David Steurer

I am a second-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

• Rounding Parallel Repetitions of Unique Games
  with Boaz Barak, Moritz Hardt, Ishay Haviv,
  Anup Rao, and Oded Regev.
• Unique Games on Expanding Constraints Graphs are Easy
  with Sanjeev Arora, Subhash Khot, Alexandra Kolla,
  Madhur Tulsiani, and Nisheeth Vishnoi.
  STOC 2008: PDF (to appear)  
• Asymptotically Optimal Hitting Sets Against Polynomials
  with Markus Bläser, and Moritz Hardt.
  ICALP 2008: PDF (to appear)
• The Interval Liar Game
  with Benjamin Doerr, and Johannes Lengler.
  ISAAC 2006: 318-327. PDF (Springer)
  Electr. Notes Discr. Math. 28 (2007): 425-432. Abstract (Elsevier)
• Tight Bounds for the Min-max Boundary
  Decomposition Cost of Weighted Graphs.
  SPAA 2006: 197-206. PDF (ACM), PDF/PS (ArXiv)
• An Asymptotic Approximation Scheme
  for Multigraph Edge Coloring
  with Peter Sanders.
  SODA 2005: 897-906. PDF (ACM, preliminary)
  awarded with the Günter-Hotz Medal 2006.
  ACM Transactions on Algorithms: to appear. PDF (preprint, most recent)

Contact