Improved clustering and robust moment estimation via sum-of-squareswith Pravesh Kothari, Jacob Steinhardt. STOC 2018. (to appear).
Bayesian estimation from few samples: community detection and related problemswith Sam Hopkins. FOCS 2017. (to appear).
The power of sum-of-squares for detecting hidden structurewith Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm. FOCS 2017. (to appear).
Fast and robust tensor decomposition with applications to dictionary learningwith Tselil Schramm. COLT 2017. pdf
Quantum entanglement, sum of squares, and the log rank conjecturewith Boaz Barak, Pravesh Kothari. STOC 2017. pdf(to appear).
Polynomial-time tensor decompositions with sum-of-squareswith Tengyu Ma, Jonathan Shi. FOCS 2016. pdf
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorswith Sam Hopkins, Tselil Schramm, Jonathan Shi. STOC 2016. pdf
Tensor principal component analysis via sum-of-squares proofswith Sam Hopkins, Jonathan Shi. COLT 2015. pdf
Beating the random assignment on constraint satisfaction problems of bounded degreewith 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 relaxationswith James R. Lee, Prasad Raghavendra. STOC 2015. pdfBest Paper Award at STOC 2015.
Dictionary learning and tensor decomposition via the sum-of-squares methodwith Boaz Barak, Jonathan Kelner. STOC 2015. pdf
On the power of symmetric LP and SDP relaxationswith James R. Lee, Prasad Raghavendra, Ning Tan. CCC 2014. pdf
A parallel repetition theorem for entangled projection gameswith Irit Dinur, Thomas Vidick. CCC 2014, QIP 2014. pdfInvited to CCC 2014 special issue.
Approximate constraint satisfaction requires large LP relaxationswith Siu On Chan, James R. Lee, Prasad Raghavendra. FOCS 2013. pdfInvited to FOCS 2013 special issue, Accepted to JACM.
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfactionwith Boaz Barak, Guy Kindler. ITCS 2013. pdf
Approximation limits of linear programs (beyond hierarchies)with Gábor Braun, Samuel Fiorini, Sebastian Pokutta. FOCS 2012. pdf
Hypercontractivity, sum-of-squares proofs, and applicationswith Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, Yuan Zhou. STOC 2012. pdfInvited to STOC 2012 special issue.
Making the long code shorterwith Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra. FOCS 2012. pdfInvited to FOCS 2012 special issue.
Rounding semidefinite programming hierarchies via global correlationwith Boaz Barak, Prasad Raghavendra. FOCS 2011. pdf
Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansionManuscript. pdf
Finding almost-perfect graph bisectionswith Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, Yuan Zhou. ICS 2011. pdf
Subsampling mathematical relaxations and average-case complexitywith Boaz Barak, Moritz Hardt, Thomas Holenstein. SODA 2011. pdf
On the complexity of Unique Games and graph expansionDissertation. pdfHonorable Mention for ACM Doctoral Dissertation Award 2011.
Subexponential algorithms for unique games and related problemswith Sanjeev Arora, Boaz Barak. FOCS 2010, JACM. pdfBest Paper Award at FOCS 2010.
Graph expansion and the Unique Games Conjecturewith Prasad Raghavendra. STOC 2010. pdfInvited to STOC 2010 special issue.
Approximations for the isoperimetric and spectral profile of graphs and related parameterswith Prasad Raghavendra, Prasad Tetali. STOC 2010. pdf
Message-passing algorithms and improved LP decodingwith Sanjeev Arora, Constantinos Daskalakis. STOC 2009, IEEE Transactions on Information Theory 58(12). pdf
Rounding parallel repetitions of Unique Gameswith Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev. FOCS 2008. pdf
Unique Games on expanding constraints graphs are easywith Sanjeev Arora, Subhash Khot, Alexandra Kolla, Madhur Tulsiani, Nisheeth Vishnoi. STOC 2008. pdf
Asymptotically optimal hitting sets against polynomialswith Markus Bläser, Moritz Hardt. ICALP (1) 2008. pdf
The interval liar gamewith Benjamin Doerr, Johannes Lengler. ISAAC 2006, Electr. Notes Discr. Math. 28 (2007). pdf
An asymptotic approximation scheme for multigraph edge coloringwith Peter Sanders. SODA 2005, ACM Trans. Algorithms 4, 2 (2008). pdfAwarded with the Günter-Hotz Medal 2006, Invited to SODA 2005 special issue.