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 9 of 9 for “"Hardness of Approximation"”.
-
On approximating projection games
… problem (also known as LABEL COVER) is a problem of great significance in the field of hardness of approximation since almost all NP-hardness of approximation results known today are derived from the NP-hardness of approximation of projection games. Hence, it is important to determine the exact …
-
Graphs, Principal Minors, and Eigenvalue Problems
… point processes (DPPs), we consider the classes of symmetric and signed DPPs, respectively, and in both cases connect the problem of learning the parameters of a DPP to a related matrix recovery problem. Next, we consider two conjectures in spectral graph theory regarding the spread of a graph, …
-
Algorithms for strategic agents
… reported by strategic agents with interests of their own? The unique challenge stems from the fact that the agents may choose to lie about the input in order to manipulate the behavior of the algorithm for their own interests, and tools from Game Theory are therefore required in order to …
-
Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring
… A closed quasigeodesic on the surface of a polyhedron is a loop which can everywhere locally be unfolded to a straight line: thus, it's straight on faces, uniquely determined on edges, and has as much flexibility at a vertex as that vertex's curvature. On any polyhedron, at least three …
-
New error correcting codes from lifting
… protecting information from noise. The theory of error correcting codes studies the range of parameters achievable by such codes, as well as the efficiency with which one can encode and decode them. In recent years, attention has focused on the study of sublinear-time algorithms for various …
-
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 …
-
Modern Interactive Proofs
In this thesis, we study several extensions of the concept of interactive proofs. First, we consider non-signaling multi-prover interactive proofs. Interacting with multiple non-interacting provers increases the ability of the verifier to check the solution by asking the provers different questions …
-
On approximability and LP formulations for multicut and feedback set problems
This Dissertation was approved for publication on 2018-08-23 at 14:21.
-
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 …