Approximating NP-hard problems: efficient algorithms and their limits

Advised by Venkatesan Guruswami

Local statistics, semidefinite programming, and community detection.

Jess Banks, Sidhanth Mohanty, Prasad Raghavendra

SODA 2021List-Decodable Subspace Recovery.

*Prasad Raghavendra, Morris Yau*

COLT 2020Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4

Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu.

STOC 2020Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond.

*Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni.*

STOC 2020List Decodable Learning via Sum of Squares.

*Prasad Raghavendra, Morris Yau*

SODA 2020Extended Formulation Lower Bounds for Refuting Random CSPs.

*Jonah Brown-Cohen, Prasad Raghavendra.*

SODA 2020Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones.

*Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz.*

SODA 2019Dimension Reduction for Polynomials over Gaussian Space and Applications.

*Badih Ghazi, Pritish Kamath, Prasad Raghavendra*

CCC 2018Average Whenever You Meet: Opportunistic Protocols for Community Detection.

*Luca Becchetti, Andrea E. F. Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan.*

ESA 2018The Power of Sum-of-Squares for Detecting Hidden Structures

*Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer*

FOCS 2017On the Bit Complexity of Sum-of-Squares Proofs

*Prasad Raghavendra, Benjamin Weitz*

ICALP 2017Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

*Pravesh Kothari, Raghu Meka, Prasad Raghavendra.*

STOC 2017Strongly Refuting Random CSPs Below the Spectral Threshold

*Prasad Raghavendra, Satish Rao, Tselil Schramm*

STOC 2017Real Stability Testing

*Prasad Raghavendra, Nick Ryder, Nikhil Srivastava*

ITCS 2017A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

*Pasin Manurangsi, Prasad Raghavendra*

ICALP 2017Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

*Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm*

SODA 2016The matching problem has no small symmetric SDP

*Gabor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink*

SODA 2016Combinatorial Optimization Algorithms via Polymorphisms

*Jonah Brown-Cohen, Prasad Raghavendra*

ICALP 2016Beating the random assignment on constraint satisfaction problems of bounded degree

B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, J. Wright.

APPROX 2015Lower bounds on the size of semidefinite programming relaxations

*James Lee, Prasad Raghavendra, David Steurer*

STOC 2015 (Cowinner of the Best Paper Award)On the Power of Symmetric LP and SDP Relaxations

*James Lee, Prasad Raghavendra, David Steurer, Ning Tan*

CCC 2014Computational Limits of Matrix Completion

*Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz*

COLT 2014Gap Amplification for Small Set Expansion via Random Walks

*Prasad Raghavendra, Tselil Schramm*

APPROX 2014The Complexity of Approximating Vertex Expansion

*Anand Louis, Prasad Raghavendra, Santosh Vempala*

FOCS 2013Approximate Constraint Satisfaction Requires Large LP Relaxations

*Siu On Chan, James Lee, Prasad Raghavendra, David Steurer*

FOCS 2013Making the long code shorter, with applications to the unique games conjecture

*Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka,Prasad Raghavendra,David Steurer*

FOCS 2012Many sparse cuts via higher eigen-values

*Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala*

STOC 2012Approximating CSPs with global cardinality constraints using SDP hierarchies

*Prasad Raghavendra, Ning Tan*

SODA 2012Testing odd-cycle-freeness in boolean functions

*Arnab Bhattacharya, Elena Grigorescu, Prasad Raghavendra, Assaf Shapira*

SODA 2012Bypassing the UGC for some optimal geometric inapproximability results

*Venkatesan Guruswami,Prasad Raghavendra,Rishi Saket, Yi Wu*

SODA 2012Rounding Semidefinite Programming Hierarchies via Global Correlation

*Boaz Barak, Prasad Raghavendra, David Steurer*

FOCS 2011Reductions Between Expansion Problems

*Prasad Raghavendra, David Steurer, Madhur Tulsiani*

CCC 2012Finding almost-perfect graph bisections

*Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou*

ITCS 2011Approximating Sparsest Cut in Graphs of Bounded Treewidth

*Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra*

APPROX 2010Graph Expansion and the Unique Games Conjecture

*Prasad Raghavendra, David Steurer*

STOC 2010Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters

*Prasad Raghavendra, David Steurer, Prasad Tetali*

STOC 2010Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions

*Ilias Diakonikolas,Prahlad Harsha, Adam Klivans, Raghuvardhan Meka, Prasad Raghavendra, Rocco Servedio, Li-Yang Tang*

STOC 2010List Decoding Tensor Products and Interleaved Codes

*Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra*

STOC 2009Communication Complexity of Read-Once AC0 Formulae

*T.S.Jayram, Swastik Kopparty, Prasad Raghavendra*

CCC 2009How to Round Any CSP

*Prasad Raghavendra, David Steurer*

FOCS 2009Integrality Gaps for Strong SDP Relaxations of Unique Games

*Prasad Raghavendra, David Steurer*

FOCS 2009Agnostic Learning of Monomials by Halfspaces is Hard

*Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu*

FOCS 2009Buffer Management for Colored Packets with Deadlines

*Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda and Prasad Raghavendra*

SPAA 2009, Invited to SPAA 2009 Special IssueTowards Computing the Grothendieck Constant

*Prasad Raghavendra, David Steurer*

SODA 2009Optimal Algorithms and Inapproximability Results for Every CSP?

*Prasad Raghavendra*

STOC 2008 (Co-winner of the Best Paper award and winner of the Best Student Paper award)SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension and Metric Labeling

*Rajsekar Manokaran, Seffi Naor, Prasad Raghavendra, Roy Schwartz*

STOC 2008Constraint Satisfaction over Non Boolean Domain: Approximation Algorithms and Unique Games Hardness

*Venkatesan Guruswami, Prasad Raghavendra*

APPROX 2008Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant

*Venkatesan Guruswami, Johan HÅstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar*

SIAM Journal of Computing (conference version in STOC 2007)A 3-Query PCP over Integers

*Venkatesan Guruswami, Prasad Raghavendra*

Transactions of Computation Theory (conference version in FOCS 2006)Coarse differentiation and multi-flows in planar graphs

*James Lee, Prasad Raghavendra*

Discrete and Computational Geometry 2010 (preliminary version in APPROX 2007)A Note on Yekhanin's Locally Decodable Codes

*Prasad Raghavendra*Improved Approximation Algorithms for the Spanning Star Forest Problem

*Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh*

APPROX 2007Hardness of Learning Halfspaces with Noise

*Venkatesan Guruswami, Prasad Raghavendra.*

SIAM Journal of Computing (preliminary version in FOCS 2006)On the Optimal Communication Complexity of Multiphase Protocols for Perfect Communication

*Kannan Srinathan, N. R. Prasad, C. Pandu Rangan*

IEEE Symposium on Security and Privacy (IEEE-SP) 2007On Proactive Perfectly Secure Message Transmission

*Kannan Srinathan, Prasad Raghavendra, C. Pandu Rangan*

Australasian Conference on Security and Privacy (ACISP) 2007