David Steurer
Assistant Professor
Computer Science
Cornell University
My research area is theoretical computer science. I am interested in the complexity of combinatorial optimization problems, in approximation algorithms and hardness, and in the strengths and limitations of mathematical relaxations, especially linear and semidefinite programs. Particular topics are the Unique Games Conjecture and SDP Hierarchies.
From 2010 to 2012, I was a postdoc at Microsoft Research New England. My Ph.D. is from Princeton University (2006–10), advised by Sanjeev Arora. Before, I got a B.Sc. and M.Sc. at Saarland University (2003–06).
Thesis
-
On the Complexity of Unique Games and Graph Expansion
Understanding the complexity of approximating basic optimization problems is one of the grand challenges of theoretical computer science. In recent years, a sequence of works established that Khot's Unique Games Conjecture, if true, would settle the approximability of many of these problems, making this conjecture a central open question of the field.
The results of this thesis shed new light on the plausibility of the Unique Games Conjecture, which asserts that a certain optimization problem, called Unique Games, is hard to approximate in a specific regime.
On the one hand, we give the first confirmation of this assertion for a restricted model of computation that captures the best known approximation algorithms. The results of this thesis also demonstrate an intimate connection between the Unique Games Conjecture and approximability of graph expansion. In particular, we show that the Unique Games Conjecture is true if the expansion of small sets in graphs is hard to approximate in a certain regime. This result gives the first sufficient condition for the truth of the conjecture based on the inapproximability of a natural combinatorial problem.
On the other hand, we develop efficient approximation algorithms for certain classes of Unique Games instances, demonstrating that several previously proposed variants of the Unique Games Conjecture are false.
Finally, we develop a subexponential-time algorithm for Unique Games, showing that this problem is significantly easier to approximate than NP-hard problems like Max 3-Sat, Max 3-Lin, and Label Cover, which are unlikely to have subexponential-time algorithm achieving a non-trivial approximation guarantee. This algorithm also shows that the inapproximability results based on the Unique Games Conjecture do not rule out subexponential-time algorithms, opening the possibility for such algorithms for many basic optimization problems like Max Cut and Vertex Cover.
At the heart of our subexponential-time algorithm for Unique Games lies a novel algorithm for approximating the expansion of graphs across different scales, which might have applications beyond Unique Games, especially in the design of divide-and-conquer algorithms.
Committees
Papers
- 2013+
-
Analytical Approach to Parallel Repetition
We propose an analytical framework for studying parallel repetition, a basic product operation for one-round two-player games. In this framework, we consider a relaxation of the value of a game, $\mathrm{val}_+$, and prove that for projection games, it is both multiplicative (under parallel repetition) and a good approximation for the true value.
These two properties imply a parallel repetition bound as $$ \mathrm{val}(G^{\otimes k}) \approx \mathrm{val}_+(G^{\otimes k}) = \mathrm{val}_+(G)^{k} \approx \mathrm{val}(G)^{k}. $$
Using this framework, we can also give a short proof for the NP-hardness of Label-Cover$(1,\delta)$ for all $\delta>0$, starting from the basic PCP theorem.
We prove the following new results:
- A parallel repetition bound for projection games with small soundness. Previously, it was not known whether parallel repetition decreases the value of such games. This result implies stronger inapproximability bounds for Set-Cover and Label-Cover.
- An improved bound for few parallel repetitions of projection games, showing that Raz's counterexample is tight even for a small number of repetitions.
- We show a new reduction from general games to projection games, which allows us to prove parallel repetition bounds for general games by reduction to the case of projection games.
-
On the Optimality of Semidefinite Relaxations for Average-Case and Generalized Constraint Satisfaction
This work studies several questions about the optimality of semidefinite programming (SDP) for constraint satisfaction problems (CSPs).
First we propose the hypothesis that the well known Basic SDP relaxation is actually optimal for random instances of constraint satisfaction problems for every predicate. This unifies several conjectures proposed in the past, and suggests a unifying principle for the average-case complexity of CSPs. We provide several types of indirect evidence for the truth of this hypothesis, and also show that it (and its variants) imply several conjectures in hardness of approximation including polynomial factor hardness for the densest $k$ subgraph problem and hard instances for the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell (1993).
Second, we observe that for every predicate $P$, the basic SDP relaxation achieves the same approximation guarantee for the CSP for $P$ and for a more general problem (involving not just Boolean but constrained vector assignments), which we call the Generalized CSP for $P$. Raghavendra (2008) showed that it is UG-hard to approximate the CSP for $P$ better than this guarantee. We show that it is NP-hard to approximate the Generalized CSP for $P$ better than this guarantee.
- 2012
-
Approximation Limits of Linear Programs (beyond Hierarchies)We develop a framework for approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that $O(n^{1/2-\varepsilon})$-approximations for CLIQUE require linear programs of size $2^{n^{\Omega(\varepsilon)}}$. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem.) Moreover, we establish a similar result for approximations of semidefinite programs by linear programs. Our main ingredient is a quantitative improvement of Razborov's rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjointness matrix.
-
Making the Long Code ShorterThe long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more effcient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following:
- For any $\varepsilon > 0$, we show the existence of an $n$ vertex graph $G$ where every set of $o(n)$ vertices has expansion $1 - \varepsilon$, but $G$'s adjacency matrix has more than $\exp(\log^\delta n)$ eigenvalues larger than $1 - \varepsilon$, where $\delta$ depends only on $\varepsilon$. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has $\mathrm{poly}(\log n)$ such eigenvalues.
- A gadget that reduces unique games instances with linear constraints modulo $K$ into instances with alphabet $k$ with a blowup of $K^{\mathrm{polylog}(K)}$, improving over the previously known gadget with blowup of $2^K$.
- An $n$ variable integrality gap for Unique Games that that survives $\exp(\mathrm{poly}(\log \log n))$ rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of $\mathrm{poly}(\log \log n)$.
-
Hypercontractivity, Sum-of-Squares Proofs, and their ApplicationsWe study the computational complexity of approximating the $2$-to-$q$ norm of linear operators for $q > 2$, as well as connections of this question to issues arising in quantum information theory and in the context of Khot's Unique Games Conjecture (UGC). We show the following:
- A constant level of the Sum-of-Squares / Lasserre semidefinite programming hierarchy certifies the unsatisfiability of Unique Games instances based on the noisy cube or the short code. The previous best upper bound on the level of these instances was $\exp((log n)^{\Omega(1)})$ (for the short code). This result also separates the Sum-of-Squares hierarchy from weaker hierarchies that were known to require $\omega(1)$ levels for these instances. A key ingredient of this result is that the Sum-of-Squares hierarchy can certifies bounds on the $2$-to-$4$ norm of the projector into low-degree polynomials over the Boolean cube.
- We characterize small-set expansion of graphs in terms of $2$-to-$q$ norms of projectors into the span of their top eigenvectors. As a corollary, achieving certain “good approximations” to the $2$-to-$q$ norm is at least as hard as refuting Small-Set Expansion Hypothesis --- a close relative of the UGC. On the one hand, we show that such good approximations can be obtained in time $\exp(n^{2/q})$, generalizing the known subexponential algorithm for Small-Set Expansion. On the other hand, we show that good approximations for the $2$-to-$4$ norm require quasipolynomial time assuming that 3-SAT requires exponential time. The latter result builds on a connection to the quantum separability problem.
-
Reductions between Expansion ProblemsThe Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique Games Conjecture (Raghavendra, Steurer, STOC 2010).
Our main result is that the Small-Set Expansion Hypothesis is in fact equivalent to a variant of the Unique Games Conjecture. More precisely, the hypothesis is equivalent to the Unique Games Conjecture restricted to instance with a fairly mild condition on the expansion of small sets. Alongside, we obtain the first strong hardness of approximation results for the Balanced Separator and Minimum Linear Arrangement problems. Before, no such hardness was known for these problems even assuming the Unique Games Conjecture.
These results not only establish the Small-Set Expansion Hypothesis as a natural unifying hypothesis that implies the Unique Games Conjecture, all its consequences and, in addition, hardness results for other problems like Balanced Separator and Minimum Linear Arrangement, but our results also show that the Small-Set Expansion Hypothesis problem lies at the combinatorial heart of the Unique Games Conjecture.
The key technical ingredient is a new way of exploiting the structure of the Unique Games instances obtained from the Small-Set Expansion Hypothesis via (Raghavendra, Steurer, 2010). This additional structure allows us to modify standard reductions in a way that essentially destroys their local-gadget nature. Using this modification, we can argue about the expansion in the graphs produced by the reduction without relying on expansion properties of the underlying Unique Games instance (which would be impossible for a local-gadget reduction). - 2011
-
Rounding Semidefinite Programming Hierarchies via Global CorrelationWe show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's).
-
Subexponential Algorithms for d-to-1 Two-Prover Games and for Certifying Almost Perfect Expansion
-
Finding almost-perfect graph bisections
-
Subsampling Mathematical Relaxations and Average-case Complexity
- 2010
-
Subexponential Algorithms for Unique Games and Related ProblemsWe give a subexponential time approximation algorithm for the Unique Games problem: Given a Unique Games instance with optimal value $1-\varepsilon^6$ and alphabet size k, our algorithm finds in time $\exp(k n^\varepsilon)$ a solution of value $1-\varepsilon$.
We also obtain subexponential algorithms with similar approximation guarantees for Small-Set Expansion and Multi Cut. For Max Cut, Sparsest Cut and Vertex Cover, our techniques lead to subexponential algorithms with improved approximation guarantees on subclasses of instances.
Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While our result stops short of refuting the UGC, it does suggest that Unique Games is significantly easier than NP-hard problems such as Max 3-SAT, Label Cover and more, that are believed not to have subexponential algorithms achieving a non-trivial approximation ratio.
The main component in our algorithms is a new kind of graph decomposition that may have other applications: We show that by changing an $\varepsilon$ fraction of its edges, any regular graph on n vertices can be broken into disjoint parts such that the stochastic adjacency matrix of each part has at most $n^\varepsilon$ eigenvalues larger than $1-\varepsilon^6$. -
Improved Rounding for Parallel Repeated Unique GamesWe show a tight relation between the behavior of unique games under parallel repetition and their semidefinite value. Let $G$ be a unique game with alphabet size $k$. Suppose the semidefinite value of $G$, denoted $sdp(G)$, is at least $1-\varepsilon$. Then, we show that the optimal value $opt(G^\ell)$ of the $\ell$-fold repetition of $G$ is at least $1-O(\sqrt{\ell \varepsilon \log k})$. This bound confirms a conjecture of Barak et al. (FOCS 2008), who showed a lower bound that was worse by $\sqrt{\ell\varepsilon\log (\frac1\varepsilon)}$. A consequence of our bound is the following tight relation between the semidefinite value of $G$ and the amortized value $\overline{opt}(G):= \sup_{\ell\in\mathbb N} opt(G^\ell)^{1/\ell}$, \[ sdp(G)^{O(\log k)} \le \overline{opt}(G) \le sdp(G). \] The proof closely follows the approach of Barak et al. (2008). Our technical contribution is a natural orthogonalization procedure for nonnegative functions. The procedure has the property that it preserves distances up to an absolute constant factor. In particular, our orthogonalization avoids the additive increase in distances caused by the truncation step of Barak et al. (2008).
-
Graph Expansion and the Unique Games Conjecture
-
Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters
-
Fast SDP Algorithms for Constraint Satisfaction ProblemsThe class of constraint satisfactions problems (CSPs) contains many fundamental combinatorial optimization problems such as Max Cut and Max 3-SAT.
Recently, Raghavendra (STOC`08) showed that a certain semidefinite programming relaxation gives the best possible approximation for any CSP, assuming Khot's Unique Games Conjecture. Raghavendra and Steurer (FOCS`09) show that independent of the truth of the Unique Games Conjecture the integrality gap of this relaxation cannot be improved even by adding a large class of valid inequalities.
We present an algorithm that finds an approximate solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS`09) yields an approximation algorithm for any CSP that runs in near-linear time and has an approximation guarantee that matches the integrality gap, which is optimal assuming the Unique Games Conjecture.
Our algorithm is based a framework of Arora and Kale (STOC`07) for solving semidefinite programs. In this framework, the crucial step is to design an efficient width-bounded separation oracle. We show how to implement this oracle by solving a sequence of local linear programs. We also generalize the framework of Arora and Kale in order to deal with irregular instances more efficiently. - 2009
-
Integrality Gaps for Strong SDP Relaxations of Unique GamesBased on the work of Khot and Vishnoi (FOCS 2005), we construct the first integrality gaps for strong SDP relaxations of Unique Games. By composing these gaps with UG-hardness reductions, we obtain tight integrality gaps for strong SDP relaxations of a large class of problems including Max Cut, Max q-Cut, Max k-Sat, Max Acyclic Subgraph, and Multiway Cut.
The relaxation we consider is the standard SDP relaxation strengthened by all valid linear inequalities on up to almost a logarithmic number of variables. In addition, we apply a doubly-logarithmic number of rounds of Sherali–Adams lift-and-project.
Our techniques also yield the following non-embeddability result: There exists negative-type metrics which require doubly-logarithmic distortion to embed into $\mathrm{L}_1$, even though all sub-metrics of almost logarithmic size embed isometrically into $\mathrm{L}_1$. -
How to Round Any CSPA large number of interesting combinatorial optimization problems like Max Cut, Max k-Sat, and Unique Games fall under the class of constraint satisfaction problems (CSPs).
Recent work by Raghavendra (STOC 2008) identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently (FOCS 2009), the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e.g., in the fashion of Sherali–Adams LP hierarchies).
In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and it also achieves the gap of much stronger SDP relaxations).
The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle.
A common theme of this paper and the subsequent paper in the same conference is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by “smoothing” without changing the objective value significantly. -
Towards a study of low-complexity graphsWe propose the study of graphs that are defined by low-complexity distributed and deterministic agents. We suggest that this viewpoint may help introduce the element of individual choice in models of large scale social networks. This viewpoint may also provide interesting new classes of graphs for which to design algorithms.
We focus largely on the case where the “low complexity” computation is $\mathrm{AC}_0$. We show that this is already a rich class of graphs that includes examples of lossless expanders and power-law graphs. We give evidence that even such low complexity graphs present a formidable challenge to algorithms designers. On the positive side, we show that many algorithms from property testing and data sketching can be adapted to give meaningful results for low-complexity graphs. -
Message-Passing Algorithms and Improved LP DecodingIEEE Transactions on Information Theory: To appear. pdfLinear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance —coming close to that of iterative decoding algorithms— and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel.
Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.
An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “re-weighted” version of the min-sum algorithm, obviating the need for linear programming. Our analysis implies, in particular, that this re-weighted version of the min-sum decoder corrects up to a 0.05-fraction of errors. -
Towards Computing the Grothendieck Constant
The Grothendieck constant $K_G$ is the smallest constant such that for every $d\in \mathbb{N}$ and every matrix $A = (a_{ij})$, $$\sup_{\vec u_i,\vec v_j \in B^{(d)}} \sum_{ij} a_{ij} \langle \vec u_i , \vec v_j\rangle \leq K_G \cdot \sup_{x_i,y_j \in [-1,1]} \sum_{ij} a_{ij} x_i y_j \, , $$ where $B^{(d)}$ is the unit ball in $\mathbb{R}^d$. Despite several efforts [Krivine, Reeds], the value of the constant $K_G$ remains unknown.
The Grothendieck constant $K_G$ is precisely the integrality gap of a natural SDP relaxation for the Bipartite Quadratic Programming problem. The input to this problem is a matrix $A = (a_{ij})$ and the objective is to maximize the quadratic form $\sum_{ij} a_{ij} x_i y_j$ over $x_i, y_j \in [-1,1]$.
In this work, we apply techniques from [Raghavendra`08] to the Bipartite Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [Raghavendra`08] yields the following hardness result: Assuming the Unique Games Conjecture, it is NP-hard to approximate the Bipartite Quadratic Programming problem to any factor better than the Grothendieck constant $K_G$.
By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality, we are able to perform a tighter analysis than [Raghavendra`08]. Through this careful analysis, we obtain the following new results:
- An approximation algorithm for Bipartite Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant $K_G$ (optimal approximation ratio assuming the Unique Games Conjecture).
- We show that the Grothendieck constant $K_G$ can be computed within an error $\eta$, in time depending only on $\eta$. Specifically, for each $\eta$, we formulate an explicit finite linear program, whose optimum is $\eta$-close to the Grothendieck constant.
We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
- 2008
-
Rounding Parallel Repetitions of Unique GamesWe show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by $\mathrm{val}(G)$ the value of a two-prover unique game $G$, and by $\mathrm{sdp}(G)$ the value of a natural semidefinite program to approximate $\mathrm{val}(G)$, we prove that for every $\ell\in\mathbb{N}$, if $\mathrm{sdp}(G) \geq 1-\delta$, then $\mathrm{val}(G^{\ell}) \geq 1 - \sqrt{s\ell\delta}.$ Here, $G^{\ell}$ denotes the $\ell$-fold parallel repetition of $G$, and $s=O(\log( k/\delta))$, where $k$ denotes the alphabet size of the game. For the special case where $G$ is an XOR game (i.e., $k=2$), we obtain the same bound but with $s$ as an absolute constant. Our bounds on $s$ are optimal up to a factor of $O(\log(1/ \delta))$.
For games with a significant gap between the quantities $\mathrm{val}(G)$ and $\mathrm{sdp}(G)$, our result implies that $\mathrm{val}(G^{\ell})$ may be much larger than $\mathrm{val}(G)^{\ell}$, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS '08) has shown such an example using the max-cut game on odd cycles. Our results are based on a generalization of his techniques. -
Unique Games on Expanding Constraints Graphs are EasyWe present an efficient algorithm to find a good solution to the Unique Games problem when the constraint graph is an expander. We introduce a new analysis of the standard SDP in this case that involves correlations among distant vertices. It also leads to a parallel repetition theorem for unique games when the graph is an expander.
-
Asymptotically Optimal Hitting Sets Against Polynomials
- 2007–2005
-
The Interval Liar GameISAAC 2006: 318–327. pdf (Springer)Electr. Notes Discr. Math. 28 (2007): 425–432. pdf (Elsevier)
-
Tight Bounds for the Min-max Boundary
Decomposition Cost of Weighted Graphs -
An Asymptotic Approximation Scheme
for Multigraph Edge ColoringSODA 2005: 897–906. Awarded with the Günter-Hotz Medal 2006.
Talks
- Semidefinite Programming – Approximation & Complexity
-
Summer school on semidefinite optimization, RWTH Aachen, September 2012.
pdf (lecture 1) pdf (lecture 2) pdf (lecture 3) +- Lecture 1:
- Introduction & optimal rounding scheme for constraint satisfaction problems.
- Lecture 3:
- Rounding hierarchies via global correlation & subexponential-time algorithm for Unique Games.
- Lecture 3:
- Strong limitations of sum-of-squares methods.
- Semidefinite Programming Hierarchies and the Unique Games Conjecture
-
A survey of recent results about the power of semidefinite programming hierarchies in the context of the Unique Games Conjecture. In the past decade, this conjecture has emerged as a promising approach towards a unified resolution of many central open problems in the theory of approximation algorithms. It posits the hardness of a certain constraint satisfaction problem. We will discuss both upper and lower bounds on the complexity of this problem through the lens of semidefinite programming hierarchies.
- On the Power of Semidefinite Programming Hierarchies (with Prasad Raghavendra)
-
STOC 2012 Workshop on Unique Games Conjecture, New York, May 2012.
pdf (part 1) ppsx (part 1) pdf (part 2) ppsx (part 2) +The study of the unique games conjecture (UGC) has led to deeper understanding of the power of semidefinite programs (SDP) — in form of new algorithms, integrality gap constructions and tight hardness results. In this tutorial, we will survey some of the recent advances in approximation algorithms based on SDP hierarchies, fuelled by the UGC. The talk will include a gentle algorithmic introduction to SDP hierarchies and their limits.
Some topics we will touch upon include– a general technique towards rounding SDP hierarchies, with application to subexponential time algorithm for unique games or a related problem. This general technique has found applications to other approximation problems such as MaxBisection. The talk will explore recent work on relations between SDP hierarchies and the spectrum of the input graph and their applications to algorithms and lower bounds. We will also show why algorithms of this general type must indeed take (almost) subexponential time for unique games, and discuss how sum-of-squares type arguments might help to go beyond these limitations.
- Hypercontractivity, Sum-of-Squares Proofs, and their Applications
-
We study the computational complexity of approximating the $2$-to-$q$ norm of linear operators for $q > 2$, as well as connections of this question to issues arising in quantum information theory and in the context of Khot's Unique Games Conjecture (UGC). We show the following:
- A constant level of the Sum-of-Squares / Lasserre semidefinite programming hierarchy certifies the unsatisfiability of Unique Games instances based on the noisy cube or the short code. The previous best upper bound on the level of these instances was $\exp((log n)^{\Omega(1)})$ (for the short code). This result also separates the Sum-of-Squares hierarchy from weaker hierarchies that were known to require $\omega(1)$ levels for these instances. A key ingredient of this result is that the Sum-of-Squares hierarchy can certifies bounds on the $2$-to-$4$ norm of the projector into low-degree polynomials over the Boolean cube.
- We characterize small-set expansion of graphs in terms of $2$-to-$q$ norms of projectors into the span of their top eigenvectors. As a corollary, achieving certain “good approximations” to the $2$-to-$q$ norm is at least as hard as refuting Small-Set Expansion Hypothesis --- a close relative of the UGC. On the one hand, we show that such good approximations can be obtained in time $\exp(n^{2/q})$, generalizing the known subexponential algorithm for Small-Set Expansion. On the other hand, we show that good approximations for the $2$-to-$4$ norm require quasipolynomial time assuming that 3-SAT requires exponential time. The latter result builds on a connection to the quantum separability problem.
- Rounding Semidefinite Programming Hierarchies via Global Correlation
-
We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). Joint work with Boaz Barak, and Prasad Raghavendra.
- Semidefinite Programming Hierarchies and the Unique Games Conjecture
-
Semidefinite programming (SDP) relaxation are a form of convex relaxation that found many uses in algorithms for combinatorial optimization. In the early 1990's several researchers proposed stronger forms of SDP relaxation known as SDP hierarchies. In this talk, I will present a new way of taking algorithmic advantage of these hierarchies to solve constraint satisfaction problems for 2-variable constraints such as Label-Cover, Max-Cut, and Unique-Games.
Specifically, we show an SDP-hierarchy based algorithm that provides arbitrarily good approximation to all these problems in time $\mathrm{poly}(n)\cdot\exp(r)$, where $r$ is the number of eigenvalues in the constraint graph larger than some constant threshold (depending on the accuracy parameter and type of constraint used).
In particular we get quasipolynomial algorithms for instances whose constraint graph is hypercontractive, as is the case for all the canonical "hard instances" for Max Cut and Unique Games. This result gives more reason to consider relatively low levels of an SDP hierarchy as candidate algorithms for refuting Khot's Unique Games Conjecture.
Based on joint works with Sanjeev Arora, Boaz Barak, and Prasad Raghavendra.
- Subexponential Algorithms for Unique Games and Related Problems
-
We give a subexponential-time approximation algorithm for the Unique Games problem: Given a Unique Games instance with optimal value $1-\varepsilon^3$ and alphabet size $k$, our algorithm finds in time $\exp(k\cdot n^\varepsilon)$ a solution of constant value (say at least 0.99).
We also obtain subexponential algorithms with similar approximation guarantees for Small-Set Expansion and Multi Cut. For Max Cut, Sparsest Cut and Vertex Cover, our techniques lead to subexponential algorithms with improved approximation guarantees on interesting subclasses of instances.
Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While our result stops short of refuting the UGC, it does suggest that Unique Games is significantly easier than NP-hard problems such as Max 3-SAT, Label Cover and more, that are believed not to have subexponential algorithms achieving a non-trivial approximation ratio.
The main component in our algorithms is a new kind of graph decomposition that may have other applications: We show that every graph with $n$ vertices can be efficiently partitioned into disjoint induced subgraphs, each with at most $n^\varepsilon$ eigenvalues above $1-\varepsilon^3$, such that at most 0.01 of the edges do not respect the partition.
Joint work with Sanjeev Arora and Boaz Barak.
Contact
- dsteurer@cs.cornell.edu
- Office
- 4134 Upson Hall map
- Adminstrative Assistant
- Michelle Eighmey email
- Postal address
-
Department of Computer Science
Cornell University
Ithaca NY 14853