research interests

Algorithms and complexity theory for NP-hard optimization problems. Mathematical relaxations especially linear programming, spectral methods, and semidefinite programming. The Unique Games Conjecture and the sum-of-squares meta algorithm.

recent events

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.
Dec. 2014
Midwest Theory Day, University of Michigan, Ann Arbor.
Sep. 2014
workshop on semidefinite optimization, approximation and applications, Simons Institute, Berkeley.
Sep. 2014
lectures on extended formulations and the sum-of-squares method at Fifth Cargèse Workshop on Combinatorial Optimization, Corsica, France.
Feb. 2014
workshop on semidefinite programming and graph algorithms, ICERM, Providence.

curriculum vitæ pdf

since 2016
Institute for Advanced Study — visiting assistant professor
since 2012
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)

Polynomial-time tensor decompositions with sum-of-squares with , . FOCS 2016.
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)

Theory of Computing (CS 6810—graduate, Spring 2016)
Theory Seminar (CS 7890, Spring 2016)

program committees

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