David Steurer
I am a postdoctoral researcher at Microsoft Research New England. Next fall, I will start at Cornell University as an assistant professor.
My research area is Theoretical Computer Science. I am interested in the strengths and limitations of mathematical relaxations for basic combinatorial optimization problems.
From 2006 to 2010, I was a Ph.D. student at the Computer Science Department of Princeton University, advised by Sanjeev Arora. From 2003 through 2006, I was at the Computer Science Department of Saarland University and the nearby Max-Planck-Institut Informatik. There, I obtained a B.S. and M.S. in Computer Science. My advisors were Peter Sanders and Kurt Mehlhorn.
Publications
-
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
with Boaz Barak, Aram Harrow, Jonathan Kelner, and Yuan Zhou.
In STOC 2012: To appear. [+]Abstract: We study the computational complexity of approximating the $2$-to-$4$ norm of linear operators (defined as $\|A\|_{2\to 4} = \max_{v\neq 0}\|Av\|_4/\|v\|_2$), as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture. We show the following results:- A constant number rounds of the Lasserre hierachy for Small-Set Expansion and Unique Games provide good approximation for the same canonical integrality gap instances shown in previous works to require $\omega(1)$ levels of weaker SDP hierarchies. To our knowledge, these instances were the only candidate hard instances proposed to potentially fool the Lasserre hierarchy. Underlying these is a result that a natural SDP relaxation certifies that $\|P_d\|_{2\to 4} \leq 9^{d/4}$ where $P_d$ is the operator that projects a function $f:\{ \pm 1\}^n\to \mathbb R$ into the subspace of polynomials of degree at most $d$.
- \item A graph $G$ is a small set expander (where for sufficiently small sets of vertices, most of the adjacent edges exit the set) if and only if the operator projecting a vector to the top eigenspace of $G$'s adjacency matrix has bounded $2\to 4$ norm. As a corollary, a good approximation to the $2\to 4$ norm will refute the Small Set Expansion Conjecture — a close variant of the Unique Games Conjecture proposed by Raghavendra and Steurer (STOC'10).
- Computing the $2\to 4$ norm is equivalent in difficulty (up to some dimension dependent factors) to computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Two corollaries are that 1) the $2\to 4$ norm is NP-hard to approximate to precision inverse-polynomial in the dimension, and 2) that the analysis of Brandão, Christandl and Yard (STOC' 11) implies that a Lasserre hierarchy extension of the natural SDP for the $2\to 4$ norm provides a non-trivial additive approximation.
-
Making the Long Code Shorter, with Applications to
the Unique Games Conjecture
with Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra.
Manuscript. PDF. -
Subexponential Algorithms for d-to-1 Two-Prover Games
and for Certifying Almost Perfect Expansion
Manuscript. PDF. -
Reductions between Expansion Problems
with Prasad Raghavendra and Madhur Tulsiani.
Manuscript. PDF. [+]Abstract: The 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). -
Subexponential Algorithms for Unique Games and Related Problems
with Sanjeev Arora and Boaz Barak.
Co-Winner of Best Paper Award.
In FOCS 2010: 563—572. PDF (manuscript) PPSX (slides). [+]Abstract: We give a subexponential time approximation algorithm for the Unique Games problem: Given a Unique Games instance with optimal value $1-\epsilon^6$ and alphabet size k, our algorithm finds in time $\exp(k n^\epsilon)$ a solution of value $1-\epsilon$.
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 $\epsilon$ 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^\epsilon$ eigenvalues larger than $1-\epsilon^6$. -
Improved Rounding for Parallel Repeated Unique Games
In RANDOM 2010: 724—737. PDF (preprint). [+]Abstract: We 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-\epsilon$. Then, we show that the optimal value $opt(G^\ell)$ of the $\ell$-fold repetition of $G$ is at least $1-O(\sqrt{\ell \epsilon \log k})$. This bound confirms a conjecture of Barak et al. (FOCS 2008), who showed a lower bound that was worse by $\sqrt{\ell\epsilon\log (\frac1\epsilon)}$. 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). -
Fast SDP Algorithms for Constraint Satisfaction Problems
In SODA 2010: 684–697. PDF (preprint) [+]Abstract: The 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. -
Integrality Gaps for Strong SDP Relaxations of Unique Games
with Prasad Raghavendra.
In FOCS 2009: 575–585. PDF (manuscript), PDF (IEEE), PDF (preprint). [+]Abstract: Based 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 L1, even though all sub-metrics of almost logarithmic size embed isometrically into L1. -
How to Round Any CSP
with Prasad Raghavendra.
In FOCS 2009: 585–594. PPTX (slides), PDF (IEEE), PDF (preprint). [+]Abstract: A 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 graphs
with Sanjeev Arora and Avi Wigderson.
In ICALP (1) 2009: 119–131. PDF (Springer), PDF (preprint). [+]Abstract: We 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 AC0. 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 Decoding
with Sanjeev Arora and Constantinos Daskalakis.
In STOC 2009: 3–12. PDF (ACM), PDF (preprint). [+]Abstract: Linear 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
with Prasad Raghavendra.
In SODA 2009: 525–534. PDF (ACM), PDF (preprint). [+]Abstract: 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.
-
Rounding Parallel Repetitions of Unique Games
with Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, and Oded Regev.
In FOCS 2008: 374–383. PDF (IEEE), PDF (preprint). [+]Abstract: We 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 Easy
with Sanjeev Arora, Subhash Khot, Alexandra Kolla,
Madhur Tulsiani, and Nisheeth Vishnoi.
In STOC 2008: 21–28. PDF (ACM), PDF (preprint). [+]Abstract: We 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
with Markus Bläser, and Moritz Hardt.
In ICALP (1) 2008: 345–356. PDF (Springer), PDF (preprint). -
The Interval Liar Game
with Benjamin Doerr, and Johannes Lengler.
In ISAAC 2006: 318–327. PDF (Springer)
In Electr. Notes Discr. Math. 28 (2007): 425–432. PDF (Elsevier). -
An Asymptotic Approximation Scheme
for Multigraph Edge Coloring
with Peter Sanders.
In SODA 2005: 897–906. PDF (ACM, preliminary version)
Awarded with the Günter-Hotz Medal 2006.
In ACM Trans. Algorithms 4, 2 (2008): 1–24. PDF (ACM), PDF (preprint).
Thesis
-
On the Complexity of Unique Games and Graph Expansion
Dissertation. PDF.
Manuscripts
-
Improved Algorithms for Unique Games via Divide and Conquer
with Sanjeev Arora, Russell Impagliazzo, and William Matthews.
Manuscript. PDF (ECCC TR10-041). -
Connection between Unique Games and Multicut
with Nisheeth Vishnoi.
Manuscript. PDF (ECCC TR09-125).
Contact
| e-mail: | dsteurer at cs • princeton • edu |
| mail: |
Microsoft Research New England One Memorial Drive Cambridge, MA 02142 |