David Steurer

I am a fourth-year Ph.D. student at the Computer Science Department of Princeton University. My research area is Theoretical Computer Science. I am interested in the strengths and limitations of mathematical relaxations for combinatorial optimization problems. My advisor is 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

• Fast SDP Algorithms for Constraint Satisfaction Problems
  In SODA 2010: To appear. 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: To appear. PDF (manuscript), 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 L₁, even though all sub-metrics of almost logarithmic size embed isometrically into L₁.
• How to Round Any CSP
  with Prasad Raghavendra.
  In FOCS 2009: To appear. PPTX (slides), 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 AC₀. 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.

  We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
• 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).
• Tight Bounds for the Min-max Boundary
  Decomposition Cost of Weighted Graphs.
  In SPAA 2006: 197–206. PDF (ACM), PDF/PS (arxiv, full version).
• 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).

Manuscripts

• Graph Expansion and the Unique Games Conjecture
  with Prasad Raghavendra.
  Manuscript.
• Approximations for the Isoperimetric and Spectral Profile of Graphs
  and for Restricted Eigenvalues of Diagonally-Dominant Matrices
  with Prasad Raghavendra and Prasad Tetali.
  Manuscript.
• Subsampling Semidefinite Programs and Max-Cut on the Sphere
  with Boaz Barak, Moritz Hardt, and Thomas Holenstein.
  Manuscript.
• Improved Algorithms for Unique Games via Divide and Conquer
  with Sanjeev Arora, Russell Impagliazzo, and William Matthews.
  Manuscript.

Contact