2021

Robust Recovery for Stochastic Block Models
with Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer. FOCS 2021. PDF

Consistent regression when oblivious outliers overwhelm
with Tommaso d'Orsi, Gleb Novikov, David Steurer. ICML 2021. PDF

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

2020

Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
with Jingqiu Ding, Sam Hopkins. NeurIPS 2020. PDF
Spotlight at NeurIPS 2020

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

2019

Small-set expansion in the short-code graph and the 2-to-2 games conjecture
with Boaz Barak, Pravesh Kothari. ITCS 2019. PDF

2018

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
(merger of arxiv:1711.07465 [cs.DS] and arxiv:1711.11581 [cs.LG])

2017

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

Fast and robust tensor decomposition with applications to dictionary learning
with Tselil Schramm. COLT 2017. PDF

Exact tensor completion with sum-of-squares
with Aaron Potechin. COLT 2017. PDF

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

2016

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

2015

Tensor principal component analysis via sum-of-squares proofs
with Sam Hopkins, Jonathan Shi. COLT 2015. PDF

Beating the random assignment on constraint satisfaction problems of bounded degree
with Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright. APPROX 2015. PDF

Lower bounds on the size of semidefinite programming relaxations
with James R. Lee, Prasad Raghavendra. STOC 2015. PDF
Best Paper Award at STOC 2015

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

2014

Sum-of-squares proofs and the quest toward optimal algorithms
with Boaz Barak. ICM 2014. PDF
Survey

Rounding sum-of-squares relaxations
with Boaz Barak, Jonathan Kelner. STOC 2014. PDF

On the power of symmetric LP and SDP relaxations
with James R. Lee, Prasad Raghavendra, Ning Tan. CCC 2014. PDF

Direct product testing
with Irit Dinur. CCC 2014. PDF

A parallel repetition theorem for entangled projection games
with Irit Dinur, Thomas Vidick. CCC 2014. PDF
Invited to CCC 2014 special issue

Analytical approach to parallel repetition
with Irit Dinur. STOC 2014. PDF

2013

Approximate constraint satisfaction requires large LP relaxations
with Siu On Chan, James R. Lee, Prasad Raghavendra. FOCS 2013. PDF
Invited to FOCS 2013 special issue, Accepted to JACM

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
with Boaz Barak, Guy Kindler. ITCS 2013. PDF

2012

Approximation limits of linear programs (beyond hierarchies)
with Gábor Braun, Samuel Fiorini, Sebastian Pokutta. 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
Invited to STOC 2012 special issue

Making the long code shorter
with Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra. FOCS 2012. PDF
Invited to FOCS 2012 special issue

Reductions between expansion problems
with Prasad Raghavendra, Madhur Tulsiani. CCC 2012. PDF

2011

Rounding semidefinite programming hierarchies via global correlation
with Boaz Barak, Prasad Raghavendra. FOCS 2011. PDF

Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion
PDF
unpublished manuscript

Finding almost-perfect graph bisections
with Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, Yuan Zhou. ICS 2011. PDF

Subsampling mathematical relaxations and average-case complexity
with Boaz Barak, Moritz Hardt, Thomas Holenstein. SODA 2011. PDF

2010

On the complexity of Unique Games and graph expansion
Dissertation. PDF
Honorable Mention for ACM Doctoral Dissertation Award 2011

Subexponential algorithms for unique games and related problems
with Sanjeev Arora, Boaz Barak. FOCS 2010. PDF
Best Paper Award at FOCS 2010

Improved rounding for parallel repeated unique games
RANDOM 2010. PDF

Graph expansion and the Unique Games Conjecture
with Prasad Raghavendra. STOC 2010. PDF
Invited to STOC 2010 special issue

Approximations for the isoperimetric and spectral profile of graphs and related parameters
with Prasad Raghavendra, Prasad Tetali. STOC 2010. PDF

Fast SDP algorithms for constraint satisfaction problems
SODA 2010. PDF

2009

Integrality gaps for strong SDP relaxations of Unique Games
with Prasad Raghavendra. FOCS 2009. PDF

How to round any CSP
with Prasad Raghavendra. FOCS 2009. PDF

Towards a study of low-complexity graphs
with Sanjeev Arora, Avi Wigderson. ICALP (1) 2009. PDF

Message-passing algorithms and improved LP decoding
with Sanjeev Arora, Constantinos Daskalakis. STOC 2009. PDF

Towards computing the Grothendieck constant
with Prasad Raghavendra. SODA 2009. PDF

2008

Rounding parallel repetitions of Unique Games
with Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev. FOCS 2008. PDF

Unique Games on expanding constraints graphs are easy
with Sanjeev Arora, Subhash Khot, Alexandra Kolla, Madhur Tulsiani, Nisheeth Vishnoi. STOC 2008. PDF

Asymptotically optimal hitting sets against polynomials
with Markus Bläser, Moritz Hardt. ICALP (1) 2008. PDF

2005–2007

The interval liar game
with Benjamin Doerr, Johannes Lengler. ISAAC 2006. PDF

Tight bounds for the min-max boundary decomposition cost of weighted graphs
SPAA 2006. PDF

An asymptotic approximation scheme for multigraph edge coloring
with Peter Sanders. SODA 2005. PDF
Awarded with the Günter-Hotz Medal 2006, Invited to SODA 2005 special issue