Prasad Raghavendra

148 papers A* 47A 7B 2Misc 1Journal 82Unranked 8

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \(\boldsymbol{\sqrt {n}}\) Dimension Threshold. SIAM J. Comput. Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
2026	J	`jnl`	Improved Certificates for Independence Number in Semirandom Hypergraphs. CoRR Pravesh Kothari, Anand Louis, Rameesh Paul, Prasad Raghavendra
2025	A*	`conf`	On optimal distinguishers for Planted Clique. FOCS Ansh Nagda, Prasad Raghavendra
2025	J	`jnl`	On optimal distinguishers for Planted Clique. CoRR Ansh Nagda, Prasad Raghavendra
2025	A*	`conf`	Robust Algorithms for Recovering Planted r-Colorable Graphs. COLT Anand Louis, Rameesh Paul, Prasad Raghavendra
2025	J	`jnl`	The communication complexity of distributed estimation. CoRR Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, Mihir Singhal, Avi Wigderson
2024	A*	`conf`	Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. FOCS Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
2024	J	`jnl`	Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. CoRR Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
2024	A*	`conf`	Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. FOCS Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu
2024	J	`jnl`	Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. CoRR Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu
2024	J	`jnl`	Omnipredictors for Regression and the Approximate Rank of Convex Functions. CoRR Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, Mihir Singhal
2024	A*	`conf`	Omnipredictors for regression and the approximate rank of convex functions. COLT Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, Mihir Singhal
2024	A*	`conf`	Robust Recovery for Stochastic Block Models, Simplified and Generalized. STOC Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
2024	J	`jnl`	Robust recovery for stochastic block models, simplified and generalized. CoRR Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
2023	A*	`conf`	Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion. STOC Ronen Eldan, Dan Mikulincer, Prasad Raghavendra
2023	—	`conf`	On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited Talk). FSTTCS Prasad Raghavendra
2022	J	`jnl`	Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs. SIAM J. Comput. Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
2022	A*	`conf`	Matrix discrepancy from Quantum communication. STOC Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
2022	J	`jnl`	Noise stability on the Boolean hypercube via a renormalized Brownian motion. CoRR Ronen Eldan, Dan Mikulincer, Prasad Raghavendra
2021	J	`jnl`	Computational phase transitions in sparse planted problems? CoRR Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
2021	A*	`conf`	Local Statistics, Semidefinite Programming, and Community Detection. SODA Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
2021	J	`jnl`	Matrix Discrepancy from Quantum Communication. CoRR Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
2021	A*	`conf`	On statistical inference when fixed points of belief propagation are unstable. FOCS Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
2020	A*	`conf`	Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. STOC Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
2020	A*	`conf`	Extended Formulation Lower Bounds for Refuting Random CSPs. SODA Jonah Brown-Cohen, Prasad Raghavendra
2020	A*	`conf`	Lifting sum-of-squares lower bounds: degree-2 to degree-4. STOC Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
2020	A*	`conf`	List Decodable Learning via Sum of Squares. SODA Prasad Raghavendra, Morris Yau
2020	A*	`conf`	List Decodable Subspace Recovery. COLT Prasad Raghavendra, Morris Yau
2020	J	`jnl`	List Decodable Subspace Recovery. CoRR Prasad Raghavendra, Morris Yau
2019	J	`jnl`	Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond. CoRR Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
2019	A*	`conf`	Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones. SODA Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz
2019	J	`jnl`	Extended Formulation Lower Bounds for Refuting Random CSPs. CoRR Jonah Brown-Cohen, Prasad Raghavendra
2019	J	`jnl`	Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4. CoRR Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
2019	J	`jnl`	List Decodable Learning via Sum of Squares. CoRR Prasad Raghavendra, Morris Yau
2019	J	`jnl`	Local Statistics, Semidefinite Programming, and Community Detection. CoRR Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
2018	A	`conf`	Average Whenever You Meet: Opportunistic Protocols for Community Detection. ESA Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
2018	A	`conf`	Dimension Reduction for Polynomials over Gaussian Space and Applications. CCC Badih Ghazi, Pritish Kamath, Prasad Raghavendra
2018	J	`jnl`	High-dimensional estimation via sum-of-squares proofs. CoRR Prasad Raghavendra, Tselil Schramm, David Steurer
2018	J	`jnl`	On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. ACM Trans. Algorithms Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
2017	A*	`conf`	A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. ICALP Pasin Manurangsi, Prasad Raghavendra
2017	A*	`conf`	Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. STOC Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
2017	J	`jnl`	Dimension Reduction for Polynomials over Gaussian Space and Applications. CoRR Badih Ghazi, Pritish Kamath, Prasad Raghavendra
2017	J	`jnl`	Dimension Reduction for Polynomials over Gaussian Space and Applications. Electron. Colloquium Comput. Complex. Badih Ghazi, Pritish Kamath, Prasad Raghavendra
2017	J	`jnl`	Exponential lower bounds on spectrahedral representations of hyperbolicity cones. CoRR Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz
2017	J	`jnl`	Friend or Foe? Population Protocols can perform Community Detection. CoRR Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
2017	A*	`conf`	On the Bit Complexity of Sum-of-Squares Proofs. ICALP Prasad Raghavendra, Benjamin Weitz
2017	J	`jnl`	On the Bit Complexity of Sum-of-Squares Proofs. CoRR Prasad Raghavendra, Benjamin Weitz
2017	A	`conf`	Real Stability Testing. ITCS Prasad Raghavendra, Nick Ryder, Nikhil Srivastava
2017	A*	`conf`	Strongly refuting random CSPs below the spectral threshold. STOC Prasad Raghavendra, Satish Rao, Tselil Schramm
2017	A*	`conf`	The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2017	J	`jnl`	The matching problem has no small symmetric SDP. Math. Program. Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink
2017	J	`jnl`	The power of sum-of-squares for detecting hidden structures. CoRR Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2016	J	`jnl`	A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. CoRR Pasin Manurangsi, Prasad Raghavendra
2016	J	`jnl`	Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2016	J	`jnl`	Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs. CoRR Pravesh Kothari, Raghu Meka, Prasad Raghavendra
2016	J	`jnl`	Bypassing UGC from Some Optimal Geometric Inapproximability Results. ACM Trans. Algorithms Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
2016	A*	`conf`	Correlation Decay and Tractability of CSPs. ICALP Jonah Brown-Cohen, Prasad Raghavendra
2016	A*	`conf`	On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. SODA Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
2016	J	`jnl`	Real Stability Testing. CoRR Prasad Raghavendra, Nick Ryder, Nikhil Srivastava
2016	J	`jnl`	Strongly Refuting Random CSPs Below the Spectral Threshold. CoRR Prasad Raghavendra, Satish Rao, Tselil Schramm
2016	A*	`conf`	The matching problem has no small symmetric SDP. SODA Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink
2015	—	`conf`	Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Combinatorial Optimization Algorithms via Polymorphisms. CoRR Jonah Brown-Cohen, Prasad Raghavendra
2015	J	`jnl`	Combinatorial Optimization Algorithms via Polymorphisms. Electron. Colloquium Comput. Complex. Jonah Brown-Cohen, Prasad Raghavendra
2015	A*	`conf`	Lower Bounds on the Size of Semidefinite Programming Relaxations. STOC James R. Lee, Prasad Raghavendra, David Steurer
2015	J	`jnl`	Making the Long Code Shorter. SIAM J. Comput. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2015	J	`jnl`	The matching problem has no small symmetric SDP. CoRR Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink
2015	J	`jnl`	Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program. CoRR Prasad Raghavendra, Tselil Schramm
2014	J	`jnl`	Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. SIAM J. Comput. Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
2014	A*	`conf`	Computational Limits for Matrix Completion. COLT Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz
2014	J	`jnl`	Computational Limits for Matrix Completion. CoRR Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz
2014	—	`conf`	Gap Amplification for Small-Set Expansion via Random Walks. APPROX-RANDOM Prasad Raghavendra, Tselil Schramm
2014	J	`jnl`	Lower bounds on the size of semidefinite programming relaxations. CoRR James R. Lee, Prasad Raghavendra, David Steurer
2014	J	`jnl`	On mimicking networks representing minimum terminal cuts. Inf. Process. Lett. Arindam Khan, Prasad Raghavendra
2014	A	`conf`	On the Power of Symmetric LP and SDP Relaxations. CCC James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan
2013	A*	`conf`	Approximate Constraint Satisfaction Requires Large LP Relaxations. FOCS Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2013	J	`jnl`	Approximate Constraint Satisfaction Requires Large LP Relaxations. CoRR Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2013	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings APPROX-RANDOM Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, José D. P. Rolim
2013	J	`jnl`	Foreword to the Special Issue on SODA'11. ACM Trans. Algorithms Shuchi Chawla, Prasad Raghavendra, Dana Randall
2013	J	`jnl`	Gap Amplification for Small-Set Expansion via Random Walks. CoRR Prasad Raghavendra, Tselil Schramm
2013	J	`jnl`	Improved Approximation Algorithms for the Spanning Star Forest Problem. Algorithmica Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh
2013	J	`jnl`	The Complexity of Approximating Vertex Expansion CoRR Anand Louis, Prasad Raghavendra, Santosh S. Vempala
2013	A*	`conf`	The Complexity of Approximating Vertex Expansion. FOCS Anand Louis, Prasad Raghavendra, Santosh S. Vempala
2012	J	`jnl`	Agnostic Learning of Monomials by Halfspaces Is Hard. SIAM J. Comput. Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2012	A*	`conf`	Approximating CSPs with global cardinality constraints using SDP hierarchies. SODA Prasad Raghavendra, Ning Tan
2012	A*	`conf`	Bypassing UGC from some optimal geometric inapproximability results. SODA Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
2012	A*	`conf`	Making the Long Code Shorter. FOCS Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2012	A*	`conf`	Many sparse cuts via higher eigenvalues. STOC Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala
2012	J	`jnl`	On Mimicking Networks Representing Minimum Terminal Cuts CoRR Arindam Khan, Prasad Raghavendra, Prasad Tetali, László A. Végh
2012	A	`conf`	Reductions between Expansion Problems. CCC Prasad Raghavendra, David Steurer, Madhur Tulsiani
2012	J	`jnl`	Testing Odd-Cycle-Freeness in Boolean Functions. Comb. Probab. Comput. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2012	A*	`conf`	Testing odd-cycle-freeness in Boolean functions. SODA Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2011	—	`conf`	Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. APPROX-RANDOM Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala
2011	J	`jnl`	Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies CoRR Prasad Raghavendra, Ning Tan
2011	J	`jnl`	Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011	J	`jnl`	Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011	J	`jnl`	Buffer Management for Colored Packets with Deadlines. Theory Comput. Syst. Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra
2011	A	`conf`	Finding Almost-Perfect Graph Bisections. ICS Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
2011	B	`conf`	Generic Techniques to Round SDP Relaxations. MFCS Prasad Raghavendra
2011	J	`jnl`	List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2011	J	`jnl`	Making the long code shorter, with applications to the Unique Games Conjecture CoRR Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Many Sparse Cuts via Higher Eigenvalues CoRR Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala
2011	J	`jnl`	Rounding Semidefinite Programming Hierarchies via Global Correlation CoRR Boaz Barak, Prasad Raghavendra, David Steurer
2011	A*	`conf`	Rounding Semidefinite Programming Hierarchies via Global Correlation. FOCS Boaz Barak, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Rounding Semidefinite Programming Hierarchies via Global Correlation. Electron. Colloquium Comput. Complex. Boaz Barak, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Testing Odd-Cycle-Freeness in Boolean Functions CoRR Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2011	J	`jnl`	Testing Odd-Cycle-Freeness in Boolean Functions. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2010	J	`jnl`	Agnostic Learning of Monomials by Halfspaces is Hard CoRR Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2010	J	`jnl`	Agnostic Learning of Monomials by Halfspaces is Hard. Electron. Colloquium Comput. Complex. Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2010	J	`jnl`	Approximating Sparsest Cut in Graphs of Bounded Treewidth CoRR Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
2010	—	`conf`	Approximating Sparsest Cut in Graphs of Bounded Treewidth. APPROX-RANDOM Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
2010	A*	`conf`	Approximations for the isoperimetric and spectral profile of graphs and related parameters. STOC Prasad Raghavendra, David Steurer, Prasad Tetali
2010	A*	`conf`	Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. STOC Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
2010	J	`jnl`	Bypassing UGC from some optimal geometric inapproximability results. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
2010	J	`jnl`	Coarse Differentiation and Multi-flows in Planar Graphs. Discret. Comput. Geom. James R. Lee, Prasad Raghavendra
2010	A*	`conf`	Graph expansion and the unique games conjecture. STOC Prasad Raghavendra, David Steurer
2010	J	`jnl`	Reductions Between Expansion Problems CoRR Prasad Raghavendra, David Steurer, Madhur Tulsiani
2010	J	`jnl`	Reductions Between Expansion Problems. Electron. Colloquium Comput. Complex. Prasad Raghavendra, David Steurer, Madhur Tulsiani
2009	A*	`conf`	Agnostic Learning of Monomials by Halfspaces Is Hard. FOCS Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2009	J	`jnl`	Average sensitivity and noise sensitivity of polynomial threshold functions CoRR Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
2009	B	`conf`	Buffer management for colored packets with deadlines. SPAA Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra
2009	J	`jnl`	Hardness of Learning Halfspaces with Noise. SIAM J. Comput. Venkatesan Guruswami, Prasad Raghavendra
2009	J	`jnl`	Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra
2009	J	`jnl`	Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. ACM Trans. Comput. Theory Venkatesan Guruswami, Prasad Raghavendra
2009	A*	`conf`	How to Round Any CSP. FOCS Prasad Raghavendra, David Steurer
2009	A*	`conf`	Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. FOCS Prasad Raghavendra, David Steurer
2009	A*	`conf`	List decoding tensor products and interleaved codes. STOC Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2009	A	`conf`	On the Communication Complexity of Read-Once AC^0 Formulae. CCC T. S. Jayram, Swastik Kopparty, Prasad Raghavendra
2009	J	`jnl`	Perfectly reliable and secure message transmission tolerating mobile adversary. Int. J. Appl. Cryptogr. Arpita Patra, Ashish Choudhary, C. Pandu Rangan, Kannan Srinathan, Prasad Raghavendra
2009	A*	`conf`	Towards computing the Grothendieck constant. SODA Prasad Raghavendra, David Steurer
2008	A*	`conf`	Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. FOCS Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra
2008	J	`jnl`	Coarse Differentiation and Multi-flows in Planar Graphs. Electron. Colloquium Comput. Complex. James R. Lee, Prasad Raghavendra
2008	—	`conf`	Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. APPROX-RANDOM Venkatesan Guruswami, Prasad Raghavendra
2008	J	`jnl`	Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra
2008	J	`jnl`	List Decoding Tensor Products and Interleaved Codes CoRR Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2008	J	`jnl`	List Decoding Tensor Products and Interleaved Codes. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2008	A*	`conf`	Optimal algorithms and inapproximability results for every CSP? STOC Prasad Raghavendra
2008	A*	`conf`	Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. STOC Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz
2007	A*	`conf`	A 3-query PCP over integers. STOC Venkatesan Guruswami, Prasad Raghavendra
2007	J	`jnl`	A Note on Yekhanin's Locally Decodable Codes. Electron. Colloquium Comput. Complex. Prasad Raghavendra
2007	—	`conf`	Coarse Differentiation and Multi-flows in Planar Graphs. APPROX-RANDOM James R. Lee, Prasad Raghavendra
2007	—	`conf`	Improved Approximation Algorithms for the Spanning Star Forest Problem. APPROX-RANDOM Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh
2007	Misc	`conf`	On Proactive Perfectly Secure Message Transmission. ACISP Kannan Srinathan, Prasad Raghavendra, C. Pandu Rangan
2006	A*	`conf`	Hardness of Learning Halfspaces with Noise. FOCS Venkatesan Guruswami, Prasad Raghavendra
2006	J	`jnl`	Hardness of Learning Halfspaces with Noise. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra