phd positions

Starting Fall 2017, I will be at ETH Zurich. 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
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

since 2016
Institute for Advanced Study — visiting assistant professor
since 2012
Cornell University Department of Computer Science — assistant professor
Microsoft Research New England — postdoc
Princeton University — Ph.D., advised by Sanjeev Arora
Saarland University — undergraduate



selected papers (all papers)

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

current courses (all courses)

program committees

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