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