David Steurer

I am a third-year Ph.D. student at the Computer Science Department of Princeton University. My research area is Theoretical Computer Science. Right now, 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

• Integrality Gaps for Strong SDP Relaxations of Unique Games
  with Prasad Raghavendra.
  In FOCS 2009: To appear. PDF
• How to Round Any CSP
  with Prasad Raghavendra.
  In FOCS 2009: To appear. PDF, PPTX (slides)
• Towards a study of low-complexity graphs
  with Sanjeev Arora and Avi Wigderson.
  In ICALP 2009: To appear. PDF
• Message-Passing Algorithms and Improved LP Decoding
  with Sanjeev Arora and Constantinos Daskalakis.
  In STOC 2009: 3–12. PDF (ACM) PDF (preprint)
• Towards Computing the Grothendieck Constant
  with Prasad Raghavendra.
  In SODA 2009: 525–534. PDF (ACM)
• 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)
• 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)
• Asymptotically Optimal Hitting Sets Against Polynomials
  with Markus Bläser, and Moritz Hardt.
  In ICALP 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)

Contact