Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 21 for “"Hardness of approximation"”.
-
Algorithms and mechanism design for multi-agent systems
… problems. From a computational point of view, the presence of multiple agents introduces strategic and temporal issues, apart from enhancing the difficulty of optimization. We study the following natural mathematical models of such multi-agent problems faced in practice: a) …
-
Algorithms for budgeted auctions and multi-agent covering problems
In this thesis, we do an algorithmic study of optimization problems in budgeted auctions, and some well known covering problems in the multi-agent setting. We give new results for the design of approximation algorithms, online algorithms and hardness of approximation for these problems. Along the …
-
Algorithmic applications of propositional proof complexity
This thesis explores algorithmic applications of proof complexity theory to the areas of exact and approximation algorithms for graph problems as well as propositional reasoning systems studied commonly by the artificial intelligence and formal verification communities. On the theoretical side, our …
-
Algorithmic Game Theory
The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for algorithm design, which is to optimize in the presence of strategic behavior. Second, it has prompted us …
-
Time and space efficiency of codes and proofs
Time and space are fundamental measures of complexity. Interactive proofs, PCPs, and error correcting codes are important tools. Error correcting codes have applications from transmitting data through unreliable channels to hardness amplification. Interactive proofs and PCPs have applications from …
-
Computing Realistic Terrains from Imprecise Elevations
… In the imprecise terrain model, each vertex of a triangulated terrain has an imprecise eleva- tion value only known to lie within some interval. Under some objective function, the goal is to compute a precise terrain by assigning a single elevation value to each point, so that the objective …
-
Combating the cold-start user problem in collaborative filtering recommender systems
… recommendations to the cold user. In the absence of a good initial estimate of the preferences, the recommendations are like random probes. If the items are not chosen judiciously, both bad recommendations and too many recommendations may turn off a user. We study the cold-start user problem for …
-
Halfway to Halfspace Testing
In this thesis I study the problem of testing halfspaces under arbitrary probability distributions, using only random samples. A halfspace, or linear threshold function, is a boolean function f : Rⁿ → {±1} defined as the sign of a linear function; that is, f(x) = sign(Σᵢ wᵢxᵢ - θ) where we refer to …
-
Approximation, Proof Systems, and Correlations in a Quantum World
… computation and information: The approximability of quantum problems, quantum proof systems, and non-classical correlations in quantum systems. Our first area of study concerns the approximability of computational problems which are complete for quantum complexity classes. In the classical …
-
Oblivious and Non-oblivious Local Search for Combinatorial Optimization
… and non-oblivious approaches for a variety of problems, and derive new, improved non-oblivious local search algorithms for several problems in the area of constrained linear and monotone submodular maximization. First, we give a new, randomized approximation algorithm for maximizing a …
-
Computational applications of invariance principles
This thesis focuses on applications of classical tools from probability theory and convex analysis such as limit theorems to problems in theoretical computer science, specifically to pseudorandomness and learning theory. At first look, limit theorems, pseudorandomness and learning theory appear to …
-
Computational and communication complexity of geometric problems
In this dissertation, we investigate a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the …
-
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
Studying the approximation threshold of NP-hard optimization problems, i.e. the ratio of the objective value achievable by a polynomial time algorithm to that of the optimal solution is an important field in theoretical computer science. In the past two decades there has been significant …
-
Promise constraint satisfaction problems
… is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists under the strict …
-
Hardness results and approximation algorithms for some problems on graphs
… part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph $G$ and the goal is to find a minimum-sized set of nodes $S$ that covers all of the nodes, where a node $v$ is covered if (1) $v$ is in $S$, or (2) $v$ has a neighbor $u$ such that …
-
Intractability Results for some Computational Problems
… Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy …
-
Quantum Information and Variants of Interactive Proof Systems
For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof …
-
On approximability and LP formulations for multicut and feedback set problems
This Dissertation was approved for publication on 2018-08-23 at 14:21.
-
Approximate counting via complex zero-free regions and spectral independence
… in approximate counting that arise in the field of statistical mechanics. Building upon recent advancements in the area, our research aims to enhance our understanding of the computational complexity of sampling from the Ising and Potts models, as well as the random $k$-SAT model.</p> <p>The …
-
Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts
… first question is concerned with the validity of the Unique Games Conjecture when the constraint graph is restricted to the Boolean Hypercube. The Boolean Hypercube is a well studied graph family on which existing spectral methods fail to achieve a sub exponential time bound. We initiate the …
Page 1 of 2