Assistant Professor

Computer Science

ETH Zurich

If you are interested in pursuing a PhD in theoretical computer science, please contact me.

- Aug. 2018
- invited lecture at International Congress for Mathematicians 2018
- Jan. 2017
- Michael and Sheila Held prize
- Jan. 2017
- Winter school on sum-of-squares, UC San Diego, see
**slides** - 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.

- 2017–
- ETH Zurich — assistant professor
- 2016–2017
- Institute for Advanced Study — visiting assistant professor
- 2012–2017
- 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

- Gleb Novikov (PhD student, 2017–)
- Sam Hopkins (PhD student, 2013–2018)
- Jonathan Shi (PhD student, 2013–2018)
- Aaron Potechin (postdoc, 2017)

Exact tensor completion with sum-of-squares **COLT 2017. **pdf

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

APPROX 2018 (chair), COLT 2018, CCC 2016, APPROX 2015, FOCS 2014, STOC 2013, ICALP 2013, CATS 2013, APPROX 2012, SODA 2012.