P. Raghavendra

Most-cited papers

Optimal algorithms and inapproximability results for every CSP?
P. Raghavendra
2008Symposium on the Theory of Computing507 citations
Semantic Scholar
Graph expansion and the unique games conjecture
P. Raghavendra, David Steurer
2010Symposium on the Theory of Computing300 citations
Semantic Scholar
Rounding Semidefinite Programming Hierarchies via Global Correlation
B. Barak, P. Raghavendra, David Steurer
2011IEEE Annual Symposium on Foundations of Computer Science204 citations Open access
Semantic Scholar
Hardness of Learning Halfspaces with Noise
V. Guruswami, P. Raghavendra
2006IEEE Annual Symposium on Foundations of Computer Science201 citations
Semantic Scholar
Lower Bounds on the Size of Semidefinite Programming Relaxations
James R. Lee, P. Raghavendra, David Steurer
2014Symposium on the Theory of Computing188 citations
Semantic Scholar
Agnostic Learning of Monomials by Halfspaces Is Hard
V. Feldman, V. Guruswami, P. Raghavendra, Yi Wu
20092009 50th Annual IEEE Symposium on Foundations of Computer Science165 citations Open access
Semantic Scholar
The Power of Sum-of-Squares for Detecting Hidden Structures
Samuel B. Hopkins, Pravesh Kothari, Aaron Potechin, P. Raghavendra +2 more
2017IEEE Annual Symposium on Foundations of Computer Science164 citations Open access
Semantic Scholar
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
P. Raghavendra, Sofya Raskhodnikova, Klaus Jansen, J. Rolim
2013Lecture Notes in Computer Science140 citations
Semantic Scholar
Approximating CSPs with global cardinality constraints using SDP hierarchies
P. Raghavendra, Ning Tan
2011ACM-SIAM Symposium on Discrete Algorithms140 citations
Semantic Scholar
Reductions between Expansion Problems
P. Raghavendra, David Steurer, Madhur Tulsiani
20102012 IEEE 27th Conference on Computational Complexity140 citations
Semantic Scholar
Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu-On Chan, James R. Lee, P. Raghavendra, David Steurer
2013IEEE Annual Symposium on Foundations of Computer Science137 citations Open access
Semantic Scholar
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Pasin Manurangsi, P. Raghavendra
2016International Colloquium on Automata, Languages and Programming128 citations
Semantic Scholar
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
V. Guruswami, Rajsekar Manokaran, P. Raghavendra
20082008 49th Annual IEEE Symposium on Foundations of Computer Science122 citations
Semantic Scholar
Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
P. Raghavendra, David Steurer
20092009 50th Annual IEEE Symposium on Foundations of Computer Science106 citations
Semantic Scholar
Many sparse cuts via higher eigenvalues
Anand Louis, P. Raghavendra, P. Tetali, S. Vempala
2011Symposium on the Theory of Computing102 citations Open access
Semantic Scholar
Strongly refuting random CSPs below the spectral threshold
P. Raghavendra, Satish B. Rao, T. Schramm
2016Symposium on the Theory of Computing98 citations
Semantic Scholar
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Pravesh Kothari, Raghu Meka, P. Raghavendra
2016Symposium on the Theory of Computing81 citations
Semantic Scholar
How to Round Any CSP
P. Raghavendra, David Steurer
20092009 50th Annual IEEE Symposium on Foundations of Computer Science81 citations
Semantic Scholar
Making the Long Code Shorter
B. Barak, Parikshit Gopalan, J. Håstad, Raghu Meka +2 more
2012IEEE Annual Symposium on Foundations of Computer Science80 citations
Semantic Scholar
List Decodable Learning via Sum of Squares
P. Raghavendra, Morris Yau
2019ACM-SIAM Symposium on Discrete Algorithms73 citations Open access
Semantic Scholar
Beating the random assignment on constraint satisfaction problems of bounded degree
B. Barak, Ankur Moitra, R. O'Donnell, P. Raghavendra +6 more
2015Electron. Colloquium Comput. Complex.72 citations
Semantic Scholar
SDP Gaps and UGC Hardness for Multiway Cut , 0-Extension and Metric Labelling
Rajsekar Manokaran, Joseph, S. Naor, P. Raghavendra +2 more
200870 citations
Semantic Scholar
High-dimensional estimation via sum-of-squares proofs
P. Raghavendra, T. Schramm, David Steurer
2018International Congress of Mathematicans67 citations Open access
Semantic Scholar
On the Bit Complexity of Sum-of-Squares Proofs
P. Raghavendra, B. Weitz
2017International Colloquium on Automata, Languages and Programming62 citations
Semantic Scholar
Computational Limits for Matrix Completion
Moritz Hardt, Raghu Meka, P. Raghavendra, B. Weitz
2014Annual Conference Computational Learning Theory62 citations
Semantic Scholar
Approximations for the isoperimetric and spectral profile of graphs and related parameters
P. Raghavendra, David Steurer, P. Tetali
2010Symposium on the Theory of Computing57 citations
Semantic Scholar
List decoding tensor products and interleaved codes
Parikshit Gopalan, V. Guruswami, P. Raghavendra
2008Symposium on the Theory of Computing57 citations Open access
Semantic Scholar
Towards computing the Grothendieck constant
P. Raghavendra, David Steurer
2009ACM-SIAM Symposium on Discrete Algorithms56 citations
Semantic Scholar
Approximating np-hard problems efficient algorithms and their limits
V. Guruswami, P. Raghavendra
200954 citations
Semantic Scholar
Coarse Differentiation and Multi-flows in Planar Graphs
James R. Lee, P. Raghavendra
2007International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques53 citations Open access
Semantic Scholar
The Complexity of Approximating Vertex Expansion
Anand Louis, P. Raghavendra, S. Vempala
2013IEEE Annual Symposium on Foundations of Computer Science49 citations
Semantic Scholar
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
Ilias Diakonikolas, P. Raghavendra, R. Servedio, Li-Yang Tan
2009SIAM journal on computing (Print)47 citations Open access
Semantic Scholar
A Note on Yekhanin's Locally Decodable Codes
P. Raghavendra
2007Electron. Colloquium Comput. Complex.44 citations
Semantic Scholar
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, P. Raghavendra +1 more
2019Symposium on the Theory of Computing40 citations Open access
Semantic Scholar
Lifting sum-of-squares lower bounds: degree-2 to degree-4
Sidhanth Mohanty, P. Raghavendra, Jeff Xu
2019Symposium on the Theory of Computing40 citations Open access
Semantic Scholar
Bypassing UGC from Some Optimal Geometric Inapproximability Results
V. Guruswami, P. Raghavendra, Rishi Saket, Yi Wu
2016TALG40 citations Open access
Semantic Scholar
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
Samuel B. Hopkins, Pravesh Kothari, Aaron Potechin, P. Raghavendra +1 more
2016ACM-SIAM Symposium on Discrete Algorithms39 citations
Semantic Scholar
On mimicking networks representing minimum terminal cuts
A. Khan, P. Raghavendra, P. Tetali, L. Végh
2012Information Processing Letters39 citations Open access
Semantic Scholar
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
V. Guruswami, P. Raghavendra
2008International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques32 citations
Semantic Scholar
Local Statistics, Semidefinite Programming, and Community Detection
Jessica E. Banks, Sidhanth Mohanty, P. Raghavendra
2019ACM-SIAM Symposium on Discrete Algorithms31 citations
Semantic Scholar
Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions
Anand Louis, P. Raghavendra, P. Tetali, S. Vempala
2011International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques28 citations
Semantic Scholar
Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program
P. Raghavendra, T. Schramm
2015arXiv.org27 citations
Semantic Scholar
Making the long code shorter, with applications to the Unique Games Conjecture
B. Barak, Parikshit Gopalan, J. Håstad, Raghu Meka +2 more
2011Electron. Colloquium Comput. Complex.25 citations
Semantic Scholar
List Decodable Subspace Recovery
P. Raghavendra, Morris Yau
2020Annual Conference Computational Learning Theory24 citations
Semantic Scholar
Approximating Sparsest Cut in Graphs of Bounded Treewidth
E. Chlamtáč, Robert Krauthgamer, P. Raghavendra
2010International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques23 citations Open access
Semantic Scholar
Matrix discrepancy from Quantum communication
Samuel B. Hopkins, P. Raghavendra, Abhishek Shetty
2021Symposium on the Theory of Computing22 citations Open access
Semantic Scholar
On the Power of Symmetric LP and SDP Relaxations
James R. Lee, P. Raghavendra, David Steurer, Ning Tan
2014Cybersecurity and Cyberforensics Conference22 citations
Semantic Scholar
On Proactive Perfectly Secure Message Transmission
K. Srinathan, P. Raghavendra, C. Rangan
2007Australasian Conference on Information Security and Privacy21 citations
Semantic Scholar
Combinatorial Optimization Algorithms via Polymorphisms
Jonah Brown-Cohen, P. Raghavendra
2015Electron. Colloquium Comput. Complex.19 citations
Semantic Scholar
On the Communication Complexity of Read-Once AC^0 Formulae
T. S. Jayram, Swastik Kopparty, P. Raghavendra
20092009 24th Annual IEEE Conference on Computational Complexity18 citations Open access
Semantic Scholar