# positions

I am looking for highly motivated postdocs and PhD students with a strong background in theoretical computer science, mathematics, or statistics. If you are interested, please contact me.

# selected events (all events)

- Feb. 2020
*Swiss Winter School on Lower Bounds and Communication Complexity*for PhD students. Application deadline: November 15th 2019- Nov. 2019
- mini-course in workshop on
*Computational Aspects of Geometry*as part of*Statistics with Geometry and Topology*trimister at IMT Toulouse - Sep. 2019
- Clay Mathematics Institute (CMI) workshop
*Beyond Spectral Gaps*, University of Oxford - Jan. 2019
- focus lecture at 23rd Combinatorial Optimization Workshop, Aussois
- Aug. 2018
- invited lecture at International Congress for Mathematicians 2018
- Jan. 2018
- 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
**lecture notes** - May 2016
- Quarterly Theory Workshop: Semidefinite Programming Hierarchies and Sum of Squares, Northwestern University.

# curriculum vitæ (web / pdf)

- 2020–
- ETH Zurich — associate professor
- 2017–2020
- 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

# funding

- ERC Consolidator Grant, 2019
- Microsoft Research Faculty Fellowship, 2014
- Simons Collaboration: Algorithms and Geometry, 2014–2017
- Alfred P. Sloan Research Fellowship, 2014
- NSF CAREER Award, 2014
- NSF AF Medium 1408673, 2014

# group and alumni

- Stefan Tiegel (PhD student, 2020–now)
- Rares Buhai (PhD student, 2020–now)
- Jingqiu Ding (PhD student, 2020–now)
- Rajai Nasser (postdoc, 2020–now)
- Chih-Hung Liu (postdoc, 2020–now)
- Tommaso d'Orsi (PhD student, 2018–now)
- Gleb Novikov (PhD student, 2017–now)
- Sam Hopkins (PhD student 2013–2018; now: Miller fellow at UC Berkeley; starting 2021–2022: tenure-track assistant professor at MIT)
- Jonathan Shi (PhD student 2013–2019; now: postdoc with Luca Trevisan at Università Bocconi)
- Aaron Potechin (postdoc 2017; now: assistant professor at U Chicago)

# selected papers (all papers)

Playing Unique Games on Certified Small-Set Expanders with Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm.**STOC 2021.**PDF

SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation with Stefan Tiegel.

**SODA 2021.**PDF

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates with Tommaso d'Orsi, Gleb Novikov, Pravesh Kothari.

**FOCS 2020.**PDF

High-dimensional estimation from sum-of-squares proofs with Prasad Raghavendra, Tselil Schramm.

**ICM 2018.**PDF

Improved clustering and robust moment estimation via sum-of-squares with Pravesh Kothari, Jacob Steinhardt.

**STOC 2018.**PDF

Bayesian estimation from few samples: community detection and related problems with Sam Hopkins.

**FOCS 2017.**PDF

The power of sum-of-squares for detecting hidden structure with Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm.

**FOCS 2017.**PDF

Quantum entanglement, sum of squares, and the log rank conjecture with Boaz Barak, Pravesh Kothari.

**STOC 2017.**PDF

Polynomial-time tensor decompositions with sum-of-squares with Tengyu Ma, Jonathan Shi.

**FOCS 2016.**PDF

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors with Sam Hopkins, Tselil Schramm, Jonathan Shi.

**STOC 2016.**PDF

Lower bounds on the size of semidefinite programming relaxations with James R. Lee, Prasad Raghavendra.

**STOC 2015.**PDF

Dictionary learning and tensor decomposition via the sum-of-squares method with Boaz Barak, Jonathan Kelner.

**STOC 2015.**PDF

Sum-of-squares proofs and the quest toward optimal algorithms with Boaz Barak.

**ICM 2014.**PDF

Analytical approach to parallel repetition with Irit Dinur.

**STOC 2014.**PDF

Making the long code shorter with Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra.

**FOCS 2012.**PDF

Hypercontractivity, sum-of-squares proofs, and applications with Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, Yuan Zhou.

**STOC 2012.**PDF

On the complexity of Unique Games and graph expansion

**Dissertation.**PDF

Subexponential algorithms for unique games and related problems with Sanjeev Arora, Boaz Barak.

**FOCS 2010.**PDF

Graph expansion and the Unique Games Conjecture with Prasad Raghavendra.

**STOC 2010.**PDF

# program committees

- COLT 2020 (senior pc)
- STOC 2019
- APPROX 2018 (chair)
- COLT 2018
- CCC 2016
- APPROX 2015
- FOCS 2014
- STOC 2013
- ICALP 2013
- CATS 2013
- APPROX 2012
- SODA 2012