1,721,048 research outputs found
Expansion, Random Graphs and the Automatizability of Resolution
Full text linkWe explore the relationships between the computational problem of recognizing expander graphs, and the problem of efficiently approximating proof length in the well-known system of resolution. This program builds upon known connections between graph expansion and resolution lower bounds.
A proof system P is (quasi-)automatizable if there is a search algorithm which finds a P-proof of a given formula f in time (quasi)polynomial in the length of a shortest P-proof of f. It is open whether resolution is (quasi-)automatizable. We prove several conditional non-automatizability results for resolution modulo new conjectures concerning the complexity of identifying bipartite expander graphs. Our reductions use a natural family of formulas and exploit the well-known relationships between expansion and length of resolution proofs. Our hardness assumptions are unsupported; we survey known results as progress towards establishing their plausibility. The major contribution is a conditional hardness result for the quasi-automatizability of resolution.MAS
Spectral Methods in Extremal Combinatorics
Full text linkExtremal combinatorics studies how large a collection of objects can be if it satisfies a given set of restrictions. Inspired by a classical theorem due to Erdos, Ko and Rado, Simonovits and Sos posed the following problem: determine how large a collection of graphs on the vertex set {1,...,n} can be, if the intersection of any two of them contains a triangle. They conjectured that the largest possible collection, containing 1/8 of all graphs, consists of all graphs containing
a fixed triangle (a triangle-star). The first major contribution of this thesis is a confirmation of this conjecture.
We prove the Simonovits–Sos conjecture in the following strong form: the only triangle-intersecting families of measure at least 1/8 are triangle-stars (uniqueness), and every triangle-intersecting family of measure 1/8−e is O(e)-close to a triangle-star (stability). In order to prove the stability part of our theorem, we utilize a structure theorem for Boolean functions on {0,1}^m whose Fourier expansion is concentrated on the first t+1 levels, due to Kindler and Safra. The second major contribution of this thesis consists of two analogs of this theorem for Boolean functions on S_m whose Fourier expansion is concentrated on the first two levels. In the same way that the Kindler–Safra theorem is useful for studying triangle-intersecting
families, our structure theorems are useful for studying intersecting families of permutations, which are families in which any two permutations agree on the image of at least one point.
Using one of our theorems, we give a simple proof of the following result of Ellis, Friedgut and Pilpel: an intersecting family of permutations on S_m of size (1−e)(m−1)! is O(e)-close to a double coset, a family which consists of all permutations sending some point i to some point j.Ph
Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations
No full textThe inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.Ph
Clause Learning, Resolution Space, and Pebbling
No full textCurrently, the most effective complete SAT solvers are based on the DPLL algorithm augmented by Clause Learning. These solvers can handle many real-world problems from application areas like verification,
diagnosis, planning, and design. Clause Learning works by storing previously computed, intermediate results and then reusing them to prune the future search tree. Without Clause Learning, however, DPLL loses most of its effectiveness on real world problems. Recently there has been some work on obtaining a deeper understanding of the technique of Clause Learning. In this thesis, we contribute to the understanding of
Clause Learning, and the Resolution proof system that underlies it, in a number of ways.
We characterize Clause Learning as a new, intuitive Resolution refinement which we call CL. We then
show that CL proofs can effectively p-simulate general Resolution. Furthermore, this result holds even for
the more restrictive class of greedy, unit propagating CL proofs, which more accurately characterize Clause
Learning as it is used in practice. This result is surprising and indicates that Clause Learning is significantly
more powerful than was previously known.
Since Clause Learning makes use of previously derived clauses, it motivates the study of Resolution
space. We contribute to this area of study by proving that determining the variable space of a Resolution
derivation is PSPACE-complete. The reduction also yields a surprising exponential size/space trade-off for
Resolution in which an increase of just 3 units of variable space results in an exponential decrease in proofsize.
This result runs counter to the intuitions of many in the SAT-solving community who have generally
believed that proof-size should decrease smoothly as available space increases.
In order to prove these Resolution results, we need to make use of some intuition regarding the relationship
between Black-White Pebbling and Resolution. In fact, determining the complexity of Resolution
variable space required us to first prove that Black-White Pebbling is PSPACE-complete. The complexity
of the Black-White Pebbling Game has remained an open problem for 30 years and resisted numerous
attempts to solve it. Its solution is the primary contribution of this thesis.Ph
The Complexity of Composition: New Approaches to Depth and Space
Full text linkThe __composition__ of two given functions f and g is a fixed way of combining them into a single new function f ◦ g. A __composition theorem__ for a complexity measure s(·) states that s(f ◦ g) ≈ s(f) + s(g); in other words, computing the combined function f ◦ g is no easier (with respect to s) than computing f and g individually. If true, then we would gain a natural approach towards proving lower bounds on s(F) for an explicit F by repeatedly composing smaller hard functions in such a way that their complexities are additive by the composition theorem. We study the composition problem for two measures: __formula depth__ and __space complexity.__
The KRW conjecture [KRW95] states that the formula depth required to compute f ◦g is approximately depth(f)+depth(g), where f ◦g is the function given by replacing every input variable of f with a disjoint copy of g. This conjecture is known to imply NC1 ⊊ P. We work towards proving this conjecture by way of proving new __lifting theorems__ from query complexity to communication complexity. Our new proof of the classic result of Raz and McKenzie [RM99] allows us to intimately connect lifting to combinatorics, and in doing so we provide a novel improvement to a key parameter called the gadget size. This result also allows us to prove conditional hardness for __automating__ the __Cutting Planes__ proof system.
Cook et al. [CMW+12] introduced the __tree evaluation problem__ as a way of showing L ⊊ P; their central conjecture partially relies on showing that the space to compute a function f while remembering the output of another function g is approximately the space to compute f plus the size of g’s output. This conjecture, which we call the __z-f conjecture__, was challenged by Buhrman et al. [BCK+14], who defined a new type of space computation called __catalytic computing__ and used it to show that composition does not hold for space-bounded computation in some settings. We give further evidence against composition by using the catalytic computing framework to give the first upper bounds on tree evaluation since the problem’s definition in [CMW+12], refuting their central conjecture. Using these techniques we also prove new results on __amortized__ computation by improving constructions for __catalytic branching programs__.Ph.D
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
No full textStudying 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 development both in terms of finding good approximation algorithms, e.g. through the use of semidefinite programming and hardness of approximation, e.g. the development of Probabilistically Checkable Proofs and Unique Games Conjecture.
Trying to prove lower bounds for the approximation threshold of an optimization problem, one could take one of two approaches. In the first approach, one proves such lower bounds under a complexity assumption like P =/= NP or Unique Games Conjecture. In the second approach, one studies the behaviour of prominent algorithmic schemes, such as Linear Programming (LP) and Semidefinite Programming (SDP) relaxations for the problem of interest. There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations.
In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The relaxations come from the context of Lift-and-Project systems. There one starts from a standard (weak) relaxation from a problem and iteratively adds more constraints to make the relaxation stronger, i.e. closer to an exact formulation of the problem. We mostly study the performance of the Sherali-Adams SDP relaxations. Specifically, the main contributions of this thesis are as follows.
• We show optimal integrality gaps for the level-\Theta(n) Sherali-Adams SDP relaxation of MAX k-CSP_q(P) for any predicate P:[q]^k -> {0,1} satisfying a technical condition, which we call being promising. Our result show that for such predicates MAX k-CSP_q (P) cannot be approximated (beyond a trivial approximation) by the Sherali-Adams SDP relaxations of even very high level. Austrin and Håstad (SIAM J. Comput., 2011) show that a random predicate is almost surely promising.
• We complement the above result by showing that for some class of predicates which are not promising MAX k-CSP_q(P) can be approximated (beyond the trivial approximation) by its canonical SDP relaxation.
• We show optimal integrality gap lower bounds for level-poly(n) Sherali-Adams SDP relaxations of Quadratic Programming. We also present superconstant integrality gap lower bounds for superconstant levels of the same hierarchy for MaxCutGain.
• We show optimal integrality gap lower bounds for the level-5 Sherali-Adams SDP relaxation of Vertex Cover. We also conjecture a positivity condition on the Taylor expansion of a certain function which, if proved, shows optimal integrality gaps for any constant level of the Sherali-Adams SDP hierarchy for Vertex Cover.
• We revisit the connection between integrality gap lower bounds and the Frankl-Rödl theorem (Trans. of the AMS, 1987). We prove a new density version of that theorem which can be interpreted as a new isoperimetric inequality of the Hamming cube. Using this inequality we prove integrality gap lower bounds for the Lovász-Schrijver SDP (resp. Sherali-Adams LP) relaxation of Vertex Cover (resp. Independent Set) in degree bounded graphs.Ph
The Power of Randomness in Communication
Full text linkCommunication complexity is a model of information transfer in computation. As a tool, communication has been very successful for proving lower bounds in seemingly disparate fields such as streaming algorithms and circuit complexity. Even so, there are many aspects of the communication model that have yet to be understood.
In this thesis we focus on the role of randomness in communication. Early results in the field showed the power of randomness by demonstrating that the Equality function can be computed efficiently with randomness but not without. Subsequent papers gave examples of functions that can not be computed efficiently, even with randomness. However, the exact strength of randomness is still an open question.
In the first part of this thesis, we develop techniques to analyze variants of the randomized communication model. We study limited access to randomness, the power of the presence of an omniscient prover, and matrix-theoretic tools intimately related to randomness. Along the way we answer some open questions from the literature and pose some new ones.
In the second part of this thesis we pivot to an analysis of communication between three or more players. In this model it is known that there are some functions that have efficient randomized protocols but are hard without the power of randomness. A better understanding of which functions those are would lead to new results in a wide variety of fields, including lower bounds in the elusive counting circuits model. We analyze a function called ExactlyN which holds a pivotal role in the power of randomness in this model. Additionally, ExactlyN has connections to the field of additive combinatorics, specifically to the Corners Problem, a long-open question about the density of combinatorial structures. Our results on ExactlyN yield a new construction for the Corners Problem.Ph.D
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
Full text linkStudying 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 development both in terms of finding good approximation algorithms, e.g. through the use of semidefinite programming and hardness of approximation, e.g. the development of Probabilistically Checkable Proofs and Unique Games Conjecture.
Trying to prove lower bounds for the approximation threshold of an optimization problem, one could take one of two approaches. In the first approach, one proves such lower bounds under a complexity assumption like P =/= NP or Unique Games Conjecture. In the second approach, one studies the behaviour of prominent algorithmic schemes, such as Linear Programming (LP) and Semidefinite Programming (SDP) relaxations for the problem of interest. There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations.
In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The relaxations come from the context of Lift-and-Project systems. There one starts from a standard (weak) relaxation from a problem and iteratively adds more constraints to make the relaxation stronger, i.e. closer to an exact formulation of the problem. We mostly study the performance of the Sherali-Adams SDP relaxations. Specifically, the main contributions of this thesis are as follows.
• We show optimal integrality gaps for the level-\Theta(n) Sherali-Adams SDP relaxation of MAX k-CSP_q(P) for any predicate P:[q]^k -> {0,1} satisfying a technical condition, which we call being promising. Our result show that for such predicates MAX k-CSP_q (P) cannot be approximated (beyond a trivial approximation) by the Sherali-Adams SDP relaxations of even very high level. Austrin and Håstad (SIAM J. Comput., 2011) show that a random predicate is almost surely promising.
• We complement the above result by showing that for some class of predicates which are not promising MAX k-CSP_q(P) can be approximated (beyond the trivial approximation) by its canonical SDP relaxation.
• We show optimal integrality gap lower bounds for level-poly(n) Sherali-Adams SDP relaxations of Quadratic Programming. We also present superconstant integrality gap lower bounds for superconstant levels of the same hierarchy for MaxCutGain.
• We show optimal integrality gap lower bounds for the level-5 Sherali-Adams SDP relaxation of Vertex Cover. We also conjecture a positivity condition on the Taylor expansion of a certain function which, if proved, shows optimal integrality gaps for any constant level of the Sherali-Adams SDP hierarchy for Vertex Cover.
• We revisit the connection between integrality gap lower bounds and the Frankl-Rödl theorem (Trans. of the AMS, 1987). We prove a new density version of that theorem which can be interpreted as a new isoperimetric inequality of the Hamming cube. Using this inequality we prove integrality gap lower bounds for the Lovász-Schrijver SDP (resp. Sherali-Adams LP) relaxation of Vertex Cover (resp. Independent Set) in degree bounded graphs.Ph
Multiparty Communication Complexity
No full textCommunication complexity is an area of complexity theory that studies an abstract model of computation called a communication protocol. In a -player communication protocol, an input to a known function is partitioned into pieces of bits each, and each piece is assigned to one of the players in the protocol. The goal of the players is to evaluate the function on the distributed input by using as little communication as possible. In a Number-On-Forehead (NOF) protocol, the input piece assigned to each player is metaphorically placed on that player's forehead, so that each player sees everyone else's input but its own. In a Number-In-Hand (NIH) protocol, the piece assigned to each player is seen only by that player. Overall, the study of communication protocols has been used to obtain lower bounds and impossibility results for a wide variety of other models of computation.
Two of the main contributions presented in this thesis are negative results on the NOF model of communication, identifying limitations of NOF protocols. Together, these results consitute stepping stones towards a better fundamental understanding of this model. As the first contribution, we show that randomized NOF protocols are exponentially more powerful than deterministic NOF protocols, as long as for some constant . As the second contribution, we show that nondeterministic NOF protocols are exponentially more powerful than randomized NOF protocols, as long as for some constant .
For the third major contribution, we turn to the NIH model and we present a positive result. Informally, we show that a NIH communication protocol for a function can simulate a Stack Machine (a Turing Machine augmented with a stack) for a related function , consisting of several instances of bundled together. Using this simulation and known communication complexity lower bounds, we obtain the first known (space vs. number of passes) trade-off lower bounds for Stack Machines.Ph
Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations
Full text linkThe inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.Ph
- …
