Prasad Raghavendra

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 54

Top Venues

Publications

Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, Mihir Singhal
Omnipredictors for Regression and the Approximate Rank of Convex Functions. CoRR (2024)
Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
Robust Recovery for Stochastic Block Models, Simplified and Generalized. STOC (2024)
Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. CoRR (2024)
Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
Robust recovery for stochastic block models, simplified and generalized. CoRR (2024)
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, Mihir Singhal
Omnipredictors for regression and the approximate rank of convex functions. COLT (2024)
Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. CoRR (2024)
Prasad Raghavendra
On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited Talk). FSTTCS (2023)
Ronen Eldan, Dan Mikulincer, Prasad Raghavendra
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion. STOC (2023)
Ronen Eldan, Dan Mikulincer, Prasad Raghavendra
Noise stability on the Boolean hypercube via a renormalized Brownian motion. CoRR (2022)
Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
On statistical inference when fixed points of belief propagation are unstable. FOCS (2022)
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
Matrix discrepancy from Quantum communication. STOC (2022)
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs. SIAM J. Comput. 51 (2) (2022)
Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
Local Statistics, Semidefinite Programming, and Community Detection. SODA (2021)
Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
On statistical inference when fixed points of belief propagation are unstable. FOCS (2021)
Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
Computational phase transitions in sparse planted problems? CoRR (2021)
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
Matrix Discrepancy from Quantum Communication. CoRR (2021)
Jonah Brown-Cohen, Prasad Raghavendra
Extended Formulation Lower Bounds for Refuting Random CSPs. SODA (2020)
Prasad Raghavendra, Morris Yau
List Decodable Subspace Recovery. COLT (2020)
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. STOC (2020)
Prasad Raghavendra, Morris Yau
List Decodable Learning via Sum of Squares. SODA (2020)
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
Lifting sum-of-squares lower bounds: degree-2 to degree-4. STOC (2020)
Prasad Raghavendra, Morris Yau
List Decodable Subspace Recovery. CoRR (2020)
Prasad Raghavendra, Morris Yau
List Decodable Learning via Sum of Squares. CoRR (2019)
Jonah Brown-Cohen, Prasad Raghavendra
Extended Formulation Lower Bounds for Refuting Random CSPs. CoRR (2019)
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond. CoRR (2019)
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4. CoRR (2019)
Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
Local Statistics, Semidefinite Programming, and Community Detection. CoRR (2019)
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz
Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones. SODA (2019)
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
Dimension Reduction for Polynomials over Gaussian Space and Applications. Computational Complexity Conference (2018)
Luca Becchetti, Andrea E. F. Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
Average Whenever You Meet: Opportunistic Protocols for Community Detection. ESA (2018)
Prasad Raghavendra, Tselil Schramm, David Steurer
High-dimensional estimation via sum-of-squares proofs. CoRR (2018)
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. ACM Trans. Algorithms 14 (3) (2018)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
The power of sum-of-squares for detecting hidden structures. CoRR (2017)
Prasad Raghavendra, Benjamin Weitz
On the Bit Complexity of Sum-of-Squares Proofs. ICALP (2017)
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
Dimension Reduction for Polynomials over Gaussian Space and Applications. Electron. Colloquium Comput. Complex. 24 (2017)
Prasad Raghavendra, Satish Rao, Tselil Schramm
Strongly refuting random CSPs below the spectral threshold. STOC (2017)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS (2017)
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava
Real Stability Testing. ITCS (2017)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
Friend or Foe? Population Protocols can perform Community Detection. CoRR (2017)
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
Dimension Reduction for Polynomials over Gaussian Space and Applications. CoRR (2017)
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz
Exponential lower bounds on spectrahedral representations of hyperbolicity cones. CoRR (2017)
Prasad Raghavendra, Benjamin Weitz
On the Bit Complexity of Sum-of-Squares Proofs. CoRR (2017)
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. STOC (2017)
Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink
The matching problem has no small symmetric SDP. Math. Program. 165 (2) (2017)
Pasin Manurangsi, Prasad Raghavendra
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. ICALP (2017)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from Some Optimal Geometric Inapproximability Results. ACM Trans. Algorithms 12 (1) (2016)
Prasad Raghavendra, Satish Rao, Tselil Schramm
Strongly Refuting Random CSPs Below the Spectral Threshold. CoRR (2016)
Pasin Manurangsi, Prasad Raghavendra
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. CoRR (2016)
Jonah Brown-Cohen, Prasad Raghavendra
Correlation Decay and Tractability of CSPs. ICALP (2016)
Pravesh Kothari, Raghu Meka, Prasad Raghavendra
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs. CoRR (2016)
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava
Real Stability Testing. CoRR (2016)
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM 63 (4) (2016)
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. SODA (2016)
Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink
The matching problem has no small symmetric SDP. SODA (2016)
Jonah Brown-Cohen, Prasad Raghavendra
Combinatorial Optimization Algorithms via Polymorphisms. CoRR (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Prasad Raghavendra, Tselil Schramm
Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program. CoRR (2015)
Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink
The matching problem has no small symmetric SDP. CoRR (2015)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. SIAM J. Comput. 44 (5) (2015)
Jonah Brown-Cohen, Prasad Raghavendra
Combinatorial Optimization Algorithms via Polymorphisms. Electron. Colloquium Comput. Complex. 22 (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
James R. Lee, Prasad Raghavendra, David Steurer
Lower Bounds on the Size of Semidefinite Programming Relaxations. STOC (2015)
Prasad Raghavendra, Tselil Schramm
Gap Amplification for Small-Set Expansion via Random Walks. APPROX-RANDOM (2014)
Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. SIAM J. Comput. 43 (1) (2014)
Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz
Computational Limits for Matrix Completion. CoRR (2014)
Arindam Khan, Prasad Raghavendra
On mimicking networks representing minimum terminal cuts. Inf. Process. Lett. 114 (7) (2014)
James R. Lee, Prasad Raghavendra, David Steurer
Lower bounds on the size of semidefinite programming relaxations. CoRR (2014)
Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz
Computational Limits for Matrix Completion. COLT (2014)
James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan
On the Power of Symmetric LP and SDP Relaxations. Computational Complexity Conference (2014)
Prasad Raghavendra, Tselil Schramm
Gap Amplification for Small-Set Expansion via Random Walks. CoRR (2013)
Shuchi Chawla, Prasad Raghavendra, Dana Randall
Foreword to the Special Issue on SODA'11. ACM Trans. Algorithms 9 (3) (2013)
Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh
Improved Approximation Algorithms for the Spanning Star Forest Problem. Algorithmica 65 (3) (2013)
Anand Louis, Prasad Raghavendra, Santosh S. Vempala
The Complexity of Approximating Vertex Expansion CoRR (2013)
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. FOCS (2013)
Anand Louis, Prasad Raghavendra, Santosh S. Vempala
The Complexity of Approximating Vertex Expansion. FOCS (2013)
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. CoRR (2013)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing odd-cycle-freeness in Boolean functions. SODA (2012)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing Odd-Cycle-Freeness in Boolean Functions. Comb. Probab. Comput. 21 (6) (2012)
Arindam Khan, Prasad Raghavendra, Prasad Tetali, László A. Végh
On Mimicking Networks Representing Minimum Terminal Cuts CoRR (2012)
Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala
Many sparse cuts via higher eigenvalues. STOC (2012)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. FOCS (2012)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from some optimal geometric inapproximability results. SODA (2012)
Prasad Raghavendra, Ning Tan
Approximating CSPs with global cardinality constraints using SDP hierarchies. SODA (2012)
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
Agnostic Learning of Monomials by Halfspaces Is Hard. SIAM J. Comput. 41 (6) (2012)
Prasad Raghavendra, David Steurer, Madhur Tulsiani
Reductions between Expansion Problems. Computational Complexity Conference (2012)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation. Electron. Colloquium Comput. Complex. 18 (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture CoRR (2011)
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40 (3) (2011)
Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala
Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. APPROX-RANDOM (2011)
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. 40 (5) (2011)
Prasad Raghavendra, Ning Tan
Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies CoRR (2011)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing Odd-Cycle-Freeness in Boolean Functions CoRR (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. 18 (2011)
Prasad Raghavendra
Generic Techniques to Round SDP Relaxations. MFCS (2011)
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. 18 (2011)
Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra
Buffer Management for Colored Packets with Deadlines. Theory Comput. Syst. 49 (4) (2011)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation. FOCS (2011)
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
Finding Almost-Perfect Graph Bisections. ICS (2011)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation CoRR (2011)

Prasad Raghavendra.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Prasad Raghavendra