Assistant Professor
Computer Science Department
Cornell University

Research Interests

• computational complexity of (combinatorial) optimization problems

• approximation algorithms and hardness

• strengths and limits of mathematical relaxations, especially linear and semidefinite programs

• Unique Games Conjecture and SDP hierarchies

News

• February 10–14, 2014: workshop on semidefinite programming and graph algorithms, ICERM, Providence.

• Fall 2014: workshop on graph partitioning, semidefinite programming hierarchies, and the Unique Games Conjecture, Simons Institute, Berkeley.

Past

2010–2012

Microsoft Research New England — postdoc

2006–2010

Princeton University — Ph.D., advised by Sanjeev Arora

2003–2006

Saarland University — undergraduate

Curriculum Vitæ (pdf)

Committees

• STOC 2013
• ICALP 2013
• CATS 2013
• APPROX 2012
• SODA 2012

Recent Papers

• Approximate Constraint Satisfaction Requires Large LP Relaxations — with Siu On Chan, James R. Lee, Prasad RaghavendraFOCS 2013pdf
• Analytical Approach to Parallel Repetition — with Irit Dinurpdf
• On the Optimality of Semidefinite Relaxations for Average-Case and Generalized Constraint Satisfaction — with Boaz Barak, Guy KindlerITCS 2013pdf
• Approximation Limits of Linear Programs (beyond Hierarchies) — with Gábor Braun, Samuel Fiorini, Sebastian PokuttaFOCS 2012pdf
• Making the Long Code Shorter — with Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad RaghavendraFOCS 2012pdf

Selected Papers

• Hypercontractivity, Sum-of-Squares Proofs, and Applications — with Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, Yuan ZhouSTOC 2012pdf
• Rounding Semidefinite Programming Hierarchies via Global Correlation — with Boaz Barak, Prasad RaghavendraFOCS 2011pdf
• On the Complexity of Unique Games and Graph Expansion — Dissertationpdf
• Subexponential Algorithms for Unique Games and Related Problems — with Sanjeev Arora, Boaz BarakFOCS 2010pdf
• Graph Expansion and the Unique Games Conjecture — with Prasad RaghavendraSTOC 2010pdf

Current Courses

• Introduction to Theory of Computing (CS 4810, Fall 2013)
• Theory Seminar (CS 7890, Fall 2013)