This thesis deals with the calculation of the upper limit of the sample variance when the exact data are not known but intervals which certainly contain them are available. Generally, finding the upper limit of the sample variance knowing only interval data is an NP-hard problem, but under certain conditions imposed on the input data an appropriate efficient algorithm can be used. In this work algorithms were modified so that, even at the cost of exponential complexity, one can always find the optimal solution. The goal of this thesis is to compare selected algorithms for calculating the upper limit of sample variance over interval data from the perspective of the average computational complexity on the generated data. Using simulations it is shown that if the data meets certain conditions, the complexity of the average case is polynomial.

This master's thesis describes modified Chinese Postman Problems. These Problems are solved by (mixed) integer linear programming. The modified problems and also used approach (integer programming) belong at least to the NP complexity class. The thesis analyzes, compares and estimates computational complexity of each model. Based on this analysis, usability of described models for solving real-life problems is deduced. The models are focused on problems in urban environment. Therefore, it is possible to apply these models on problems like optimization of a waste collection or road maintenance. Graph and problem generator is programmed for purposes of this thesis.

L'Internet des objets (loT) est devenu une réalité et ses applications pressenties vont fortement augmenter la demande de vidéo mobile. En conséquence, les systèmes montent en complexité algorithmique et le portage du codage vidéo sur plates-formes embarquées devient problématique. Les nouveaux contenus vidéo 4K et 360°, venant avec des résolutions spatiales (8K, 16K) et temporelles (120 images/seconde élevées compliquent encore le problème. Il est donc nécessaire de réduire l'empreinte des nouveaux codec tels que HEVC tout en préservant les performances en compression et en qualité d'image de ces codecs, La performance énergétique limitée des batteries des systèmes embarqués pousse à proposer de nouvelle méthodes pour ajuster et contrôler la complexité et l'énergie des codecs HEVC. Ce document propose un ensemble d'études dont l'objectif est d'ajuster et de contrôler la complexité et donc la consommation énergétique de l'encodeur HEVC. Deux méthodes de prédiction de découpe de CTU sont proposées : la première basée sur une approche statistique utilisant la variance de l'image et la seconde utilisant l'intelligence artificielle. À partir de cette prédiction, une méthode est proposée pour ajuster la complexité de l'encodage HEVC. Cette solution étend l'espace de recherche autour de la prédiction et alloue la complexité dans l'image afin de minimiser les dégradations en termes de compression et de qualité. Enfin un système de contrôle temps réel de la complexité d'encodage est proposé. Il démontre l'applicabilité de contributions de ce document en maintenant la complexité d'encodage proche d'une consigne. / The Internet of Things (loT) is now a reality. Forthcoming applications will boost mobile video demand to an unprecedented level. The induced increase in computational complexity is a challenge when executing in real-time new video coding standards on embedded platforms, limited in computing, memory, and energy. New 4K UHD and 360-degree video contents coming with high spatial (SK, 16K) and temporal (120fp resolutions further complicate the problem. In this context, codecs such as HEVC (High Efficiency Vide Coding) must be worked on to reduce their complexity while preserving the bitrate and image quality. Th bounded energy density of embedded system's batteries requires designers to propose new methods scaling and controlling the complexity and energy consumption of HEVC codecs. This document presents a set of studies aiming at scaling and controlling the complexity, and therefore the energy consumption, of HEVC Intra encoding. Two methods of quad-tree partitioning prediction in "one-shot are proposed: one based on variance-aware statistic approach and one based on Machine Learning using data-mining classifiers. From the obtained prediction, a generic tunable complexity scheme of HEVC encoding is introduced. It expands the search space around the original partitioning prediction and allocates complexit in a frame while minimizing performance loss in terms of bitrate and visual quality. Finally, a real-time contr system is created that dynamically manages the encoding process to keep the encoding complexity under specific tarjet. It demonstrates the a licability of the mayor contributions of this document.

We introduce a family of logics extending the lightweight Description Logic EL, that allows us to define concepts in an approximate way. The main idea is to use a graded membership function m, which for each individual and concept yields a number in the interval [0,1] expressing the degree to which the individual belongs to the concept. Threshold concepts C~t for ~ in {<,<=,>,>=} then collect all the individuals that belong to C with degree ~t. We further study this framework in two particular directions. First, we define a specific graded membership function deg and investigate the complexity of reasoning in the resulting Description Logic tEL(deg) w.r.t. both the empty terminology and acyclic TBoxes. Second, we show how to turn concept similarity measures into membership degree functions. It turns out that under certain conditions such functions are well-defined, and therefore induce a wide range of threshold logics. Last, we present preliminary results on the computational complexity landscape of reasoning in such a big family of threshold logics.

NR 20140805

The problem of extending partial representations for an interval graph asks, whether it is possible to extend a given representation of some vertices to a valid representation of the entire graph. In this thesis we extend the recent result of Klavík et al. who proved REPEXT can be decided for proper and unit interval graphs in polynomial time. We describe properties of PI± and U± graphs and their representations and present algorithms deciding REPEXT for these classes in polynomial time. In the process, we characterize relations between the K1,3's in a graph and show that we can decide the open vertex of every K1,3. We also define notions of representation of the same order type and locally similar representations as well as intervals forced and locally forced to be closed (open) that are essential for extending partial representations when multiple types of intervals can occur in the same representation. We characterize intervals forced and locally forced to be closed (open) in a U± graph using integer gaps in the pre-representation and we construct lower bounds for the rightmost endpoint of a component in polynomial time.

This thesis studies two discrete optimization problems: ordering problems in optimal stopping theory and popular matchings. The main goal of this thesis is to find the boundary between NP-hardness and tractability for these problems, and whenever possible, designs polynomial-time algorithms for the easy cases and approximation schemes or prophet inequalities for the hard cases. In the first part of the thesis, we study ordering problems in optimal stopping theory. In the optimal stopping problem, a player is presented with 𝓃 random variables 𝑋₁, . . . , 𝑋n, whose distributions are known to the player, but not their realizations. After observing the realization of 𝑋ᵢ, the player can choose to stop and earn reward 𝑋ᵢ, or reject 𝑋ᵢ and probe the next variable 𝑋ᵢ₊₁. If 𝑋ᵢ is rejected, it cannot be accepted in the future. The goal of the player is to maximize the expected reward at stopping time. If the order of observation is fixed, the player can find the optimal stopping criteria using a dynamic program. In this thesis, we investigate the variant in which the player is able to choose the order of observation. What is the best ordering and what benefits does ordering bring? Chapter 2 introduces the optimal ordering problem in optimal stopping theory. We prove that the problem of finding an optimal ordering is NP-hard even in very restricted cases where the support of each distribution has support on at most three points. Next, we prove an FPTAS for the hardness case and provide a tractable algorithm and a prophet inequality for two-point distributions. Chapter 3 studies the optimal ordering problem when the player can choose 𝑘 > 1 rewards before stopping. We show that finding an optimal static ordering is NP-hard even for very simple two-point distributions. Next, we prove an FPTAS for the hardness case and give prophet inequalities under static and dynamic policies for two-point distributions. In the second part of the thesis, we study popular matchings. Suppose we are given a bipartite graph with independent sets 𝑨 and 𝐵. Each vertex in 𝑨 has a ranked order of preferences on the vertices in 𝐵, and vice versa. A matching 𝑴 is popular if for any other matching 𝑴′, the number of vertices that prefer 𝑴 is at least as much as the number of vertices that prefer 𝑴′. Chapter 4 studies popular matchings. In the first part, we provide a general reduction which, through minor adjustments, proves NP-Hardness for a variety of different questions, including that of finding a max-weight popular matching. In the second part, we restrict our attention to graphs of bounded treewidth and provide a tractable algorithm for finding a max-weight popular matching.

<p>Collecting user data is crucial for advancing machine learning, social science, and government policies, but the privacy of the users whose data is being collected is a growing concern. {\em Differential Privacy (DP)} has emerged as the most standard notion for privacy protection with robust mathematical guarantees. Analyzing such massive amounts of data in a privacy-preserving manner motivates the need to study differentially-private algorithms that are also super-efficient.  </p> <p><br></p> <p>This thesis initiates a systematic study of differentially-private sublinear-time and sublinear-space algorithms. The contributions of this thesis are two-fold. First, we design some of the first differentially private sublinear algorithms for many fundamental problems. Second, we develop general DP techniques for designing differentially-private sublinear algorithms. </p> <p><br></p> <p>We give the first DP sublinear algorithm for clustering by generalizing a subsampling framework from the non-DP sublinear-time literature. We give the first DP sublinear algorithm for estimating the maximum matching size. Our DP sublinear algorithm for estimating the average degree of the graph achieves a better approximation than previous works. We give the first DP algorithm for releasing $L_2$-heavy hitters in the sliding window model and a pure $L_1$-heavy hitter algorithm in the same model, which improves upon previous works.  </p> <p><br></p> <p>We develop general techniques that address the challenges of designing sublinear DP algorithms. First, we introduce the concept of Coupled Global Sensitivity (CGS). Intuitively, the CGS of a randomized algorithm generalizes the classical  notion of global sensitivity of a function, by considering a coupling of the random coins of the algorithm when run on neighboring inputs. We show that one can achieve pure DP by adding Laplace noise proportional to the CGS of an algorithm. Second, we give a black box DP transformation for a specific class of approximation algorithms. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function has small global sensitivity. In particular, this transformation gives rise to sublinear DP algorithms for many problems, including triangle counting, the weight of the minimum spanning tree, and norm estimation.</p>

No description available.

<p dir="ltr">We analyze the query complexity of multiple search problems.</p><p dir="ltr">Firstly, we provide lower bounds on the complexity of "Local Search". In local search we are given a graph G and oracle access to a function f mapping the vertices to numbers, and seek a local minimum of f; i.e. a vertex v such that f(v) <= f(u) for all neighbors u of v. We provide separate lower bounds in terms of several graph parameters, including congestion, expansion, separation number, mixing time of a random walk, and spectral gap. To aid in showing these bounds, we design and use an improved relational adversary method for classical algorithms, building on the prior work of Scott Aaronson. We also obtain some quantum bounds using the traditional strong weighted adversary method.</p><p dir="ltr">Secondly, we show a multiplicative duality gap for Yao's minimax lemma by studying unordered search. We then go on to give tighter than asymptotic bounds for unordered and ordered search in rounds. Inspired by a connection through sorting with rank queries, we also provide tight asymptotic bounds for proportional cake cutting in rounds.</p>