Assistant Professor

Department of Computer Science

Cornell University

# Research Interests

computational complexity of (combinatorial) optimization problems

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

# Events

January 2015: 18th Midrasha Mathematicae: In and Around Combinatorics, Israel Institute for Advanced Studies, Jerusalem.

December 6, 2014: Midwest Theory Day, University of Michigan, Ann Arbor.

September 2014: workshop on semidefinite optimization, approximation and applications, Simons Institute, Berkeley.

September 2014: lectures on extended formulations and the sum-of-squares method at Fifth Cargèse Workshop on Combinatorial Optimization, Corsica, France.

February 2014: workshop on semidefinite programming and graph algorithms, ICERM, Providence.

# Past

- 2010–2012
- Microsoft Research New England — postdoc
- 2006–2010
- Princeton University — Ph.D., advised by Sanjeev Arora
- 2003–2006
- Saarland University — undergraduate

# Group

- Sam Hopkins (PhD student)
- Jonathan Shi (PhD student)
- Aaron Potechin (postdoc)

# Committees

# Funding

- Microsoft Research Faculty Fellowship, 2014
- NSF CAREER Award, 2014
- Alfred P. Sloan Research Fellowship, 2014
- Simons Collaboration: Algorithms and Geometry, 2014
- NSF AF Medium 1408673, 2014

# Selected Papers

- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors — STOC 2016pdf
- Lower bounds on the size of semidefinite programming relaxations — STOC 2015pdf
- Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method — STOC 2015pdf
- Sum-of-Squares Proofs and the Quest toward Optimal Algorithms — ICM 2014pdf
- Rounding Sum-of-Squares Relaxations — STOC 2014pdf
- Analytical Approach to Parallel Repetition — STOC 2014pdf
- Approximate Constraint Satisfaction Requires Large LP Relaxations — FOCS 2013pdf
- Hypercontractivity, Sum-of-Squares Proofs, and Applications — STOC 2012pdf
- Rounding Semidefinite Programming Hierarchies via Global Correlation — FOCS 2011pdf
- On the Complexity of Unique Games and Graph Expansion — Dissertationpdf
- Subexponential Algorithms for Unique Games and Related Problems — FOCS 2010pdf
- Graph Expansion and the Unique Games Conjecture — STOC 2010pdf

# Current Courses

- Introduction to Computational Complexity (CS 4814, Fall 2015)
- Theory Seminar (CS 7890, Fall 2015)