phd positions

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

recent events (all events)

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.

curriculum vitæ pdf

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

funding

group

selected papers (all papers)

Improved clustering and robust moment estimation via sum-of-squares with , . STOC 2018.
Bayesian estimation from few samples: community detection and related problems with . FOCS 2017.
The power of sum-of-squares for detecting hidden structure with , , , , . FOCS 2017.
Fast and robust tensor decomposition with applications to dictionary learning with . COLT 2017. pdf
Exact tensor completion with sum-of-squares with . COLT 2017. pdf
Quantum entanglement, sum of squares, and the log rank conjecture with , . STOC 2017. pdf
Polynomial-time tensor decompositions with sum-of-squares with , . FOCS 2016. pdf
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors with , , . STOC 2016. pdf
Lower bounds on the size of semidefinite programming relaxations with , . STOC 2015. pdf
Dictionary learning and tensor decomposition via the sum-of-squares method with , . STOC 2015. pdf
Sum-of-squares proofs and the quest toward optimal algorithms with . ICM 14. pdf
Analytical approach to parallel repetition with . STOC 2014. pdf
Making the long code shorter with , , , , . FOCS 2012. pdf
Hypercontractivity, sum-of-squares proofs, and applications with , , , , . STOC 2012. pdf
On the complexity of Unique Games and graph expansion Dissertation. pdf
Subexponential algorithms for unique games and related problems with , . FOCS 2010, JACM. pdf
Graph expansion and the Unique Games Conjecture with . STOC 2010. pdf

program committees

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