Associate Professor
Computer Science
ETH Zurich

photo

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

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