Assistant Professor

Computer Science

IAS & Cornell Univ.

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.

- Jan. 2017
- Winter school on sum-of-squares, UC San Diego
- Sep. 2016
- Seminar on sum-of-squares at Princeton University with
**lectures notes** - 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.

- 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

Proofs, beliefs, and algorithms through the lens of sum-of-squares (COS 597F—graduate seminar, Fall 2016)

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