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 2021
List-Decodable Subspace Recovery.
Prasad Raghavendra, Morris Yau
COLT 2020
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu.
STOC 2020
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond.
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni.
STOC 2020
List Decodable Learning via Sum of Squares.
Prasad Raghavendra, Morris Yau
SODA 2020
Extended Formulation Lower Bounds for Refuting Random CSPs.
Jonah Brown-Cohen, Prasad Raghavendra.
SODA 2020
Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones.
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz.
SODA 2019
Dimension Reduction for Polynomials over Gaussian Space and Applications.
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
CCC 2018
Average 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 2018
The Power of Sum-of-Squares for Detecting Hidden Structures
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
FOCS 2017
On the Bit Complexity of Sum-of-Squares Proofs
Prasad Raghavendra, Benjamin Weitz
ICALP 2017
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
Pravesh Kothari, Raghu Meka, Prasad Raghavendra.
STOC 2017
Strongly Refuting Random CSPs Below the Spectral Threshold
Prasad Raghavendra, Satish Rao, Tselil Schramm
STOC 2017
Real Stability Testing
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava
ITCS 2017
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Pasin Manurangsi, Prasad Raghavendra
ICALP 2017
Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program
Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm
SODA 2016
The 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 2016
Combinatorial Optimization Algorithms via Polymorphisms
Jonah Brown-Cohen, Prasad Raghavendra
ICALP 2016
Beating 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 2015
Lower 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 2014
Computational Limits of Matrix Completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz
COLT 2014
Gap Amplification for Small Set Expansion via Random Walks
Prasad Raghavendra, Tselil Schramm
APPROX 2014
The Complexity of Approximating Vertex Expansion
Anand Louis, Prasad Raghavendra, Santosh Vempala
FOCS 2013
Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu On Chan, James Lee, Prasad Raghavendra, David Steurer
FOCS 2013
Making the long code shorter, with applications to the unique games conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka,Prasad Raghavendra,David Steurer
FOCS 2012
Many sparse cuts via higher eigen-values
Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala
STOC 2012
Approximating CSPs with global cardinality constraints using SDP hierarchies
Prasad Raghavendra, Ning Tan
SODA 2012
Testing odd-cycle-freeness in boolean functions
Arnab Bhattacharya, Elena Grigorescu, Prasad Raghavendra, Assaf Shapira
SODA 2012
Bypassing the UGC for some optimal geometric inapproximability results
Venkatesan Guruswami,Prasad Raghavendra,Rishi Saket, Yi Wu
SODA 2012
Rounding Semidefinite Programming Hierarchies via Global Correlation
Boaz Barak, Prasad Raghavendra, David Steurer
FOCS 2011
Reductions Between Expansion Problems
Prasad Raghavendra, David Steurer, Madhur Tulsiani
CCC 2012
Finding almost-perfect graph bisections
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
ITCS 2011
Approximating Sparsest Cut in Graphs of Bounded Treewidth
Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
APPROX 2010
Graph Expansion and the Unique Games Conjecture
Prasad Raghavendra, David Steurer
STOC 2010
Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters
Prasad Raghavendra, David Steurer, Prasad Tetali
STOC 2010
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
Ilias Diakonikolas,Prahlad Harsha, Adam Klivans, Raghuvardhan Meka, Prasad Raghavendra, Rocco Servedio, Li-Yang Tang
STOC 2010
List Decoding Tensor Products and Interleaved Codes
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
STOC 2009
Communication Complexity of Read-Once AC0 Formulae
T.S.Jayram, Swastik Kopparty, Prasad Raghavendra
CCC 2009
How to Round Any CSP
Prasad Raghavendra, David Steurer
FOCS 2009
Integrality Gaps for Strong SDP Relaxations of Unique Games
Prasad Raghavendra, David Steurer
FOCS 2009
Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
FOCS 2009
Buffer Management for Colored Packets with Deadlines
Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda and Prasad Raghavendra
SPAA 2009, Invited to SPAA 2009 Special Issue
Towards Computing the Grothendieck Constant
Prasad Raghavendra, David Steurer
SODA 2009
Optimal 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 2008
Constraint Satisfaction over Non Boolean Domain: Approximation Algorithms and Unique Games Hardness
Venkatesan Guruswami, Prasad Raghavendra
APPROX 2008
Beating 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 2007
Hardness 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) 2007
On Proactive Perfectly Secure Message Transmission
Kannan Srinathan, Prasad Raghavendra, C. Pandu Rangan
Australasian Conference on Security and Privacy (ACISP) 2007