Assistant Professor

Computer Science

Cornell University

Algorithms and complexity theory for NP-hard optimization problems. Mathematical relaxations especially linear programming, spectral methods, and semidefinite programming. The Unique Games Conjecture and the sum-of-squares meta algorithm.

- May 2016
- Quarterly Theory Workshop: Semidefinite Programming Hierarchies and Sum of Squares, Northwestern University.
- Jan. 2015
- 18th Midrasha Mathematicae: In and Around Combinatorics, Israel Institute for Advanced Studies, Jerusalem.
- Dec. 2014
- Midwest Theory Day, University of Michigan, Ann Arbor.
- Sep. 2014
- workshop on semidefinite optimization, approximation and applications, Simons Institute, Berkeley.
- Sep. 2014
- lectures on extended formulations and the sum-of-squares method at Fifth Cargèse Workshop on Combinatorial Optimization, Corsica, France.
- Feb. 2014
- workshop on semidefinite programming and graph algorithms, ICERM, Providence.

- since 2016
- Institute for Advanced Study — visiting assistant professor
- since 2012
- Cornell University Department of Computer Science — assistant professor
- 2010–2012
- Microsoft Research New England — postdoc
- 2006–2010
- Princeton University — Ph.D., advised by Sanjeev Arora
- 2003–2006
- Saarland University — undergraduate

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

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

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors **STOC 2016. **pdf

Analytical approach to parallel repetition **STOC 2014. **pdf

Making the long code shorter **FOCS 2012. **pdf

On the complexity of Unique Games and graph expansion **Dissertation. **pdf

Subexponential algorithms for unique games and related problems **FOCS 2010, JACM. **pdf

Theory of Computing (CS 6810—graduate, Spring 2016)

Theory Seminar (CS 7890, Spring 2016)

CCC 2016, APPROX 2015, FOCS 2014, STOC 2013, ICALP 2013, CATS 2013, APPROX 2012, SODA 2012.