Prasad Raghavendra

CoRR, May, 2025

Robust Algorithms for Recovering Planted r-Colorable Graphs.

[BibT_eX]

[DOI]

Anand Louis

Rameesh Paul

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

2024

Omnipredictors for Regression and the Approximate Rank of Convex Functions.

[BibT_eX]

[DOI]

CoRR, 2024

Robust Recovery for Stochastic Block Models, Simplified and Generalized.

[BibT_eX]

[DOI]

David X. Wu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold.

[BibT_eX]

[DOI]

Jun-Ting Hsieh

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Omnipredictors for regression and the approximate rank of convex functions.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion.

[BibT_eX]

[DOI]

Ronen Eldan

Dan Mikulincer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

Matrix discrepancy from Quantum communication.

[BibT_eX]

[DOI]

Samuel B. Hopkins

Abhishek Shetty

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Computational phase transitions in sparse planted problems?

[BibT_eX]

[DOI]

Siqi Liu

CoRR, 2021

Local Statistics, Semidefinite Programming, and Community Detection.

[BibT_eX]

[DOI]

Jess Banks

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On statistical inference when fixed points of belief propagation are unstable.

[BibT_eX]

[DOI]

Siqi Liu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Lifting sum-of-squares lower bounds: degree-2 to degree-4.

[BibT_eX]

[DOI]

Jeff Xu

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond.

[BibT_eX]

[DOI]

Yeshwanth Cherapanamjeri

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

List Decodable Learning via Sum of Squares.

[BibT_eX]

[DOI]

Morris Yau

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Extended Formulation Lower Bounds for Refuting Random CSPs.

[BibT_eX]

[DOI]

Jonah Brown-Cohen

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

List Decodable Subspace Recovery.

[BibT_eX]

[DOI]

Morris Yau

Proceedings of the Conference on Learning Theory, 2020

2019

Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

High-dimensional estimation via sum-of-squares proofs.

[BibT_eX]

[DOI]

CoRR, 2018

Average Whenever You Meet: Opportunistic Protocols for Community Detection.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Dimension Reduction for Polynomials over Gaussian Space and Applications.

[BibT_eX]

[DOI]

Badih Ghazi

Pritish Kamath

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Friend or Foe? Population Protocols can perform Community Detection.

[BibT_eX]

[DOI]

CoRR, 2017

Strongly refuting random CSPs below the spectral threshold.

[BibT_eX]

[DOI]

Satish Rao

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Raghu Meka

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Real Stability Testing.

[BibT_eX]

[DOI]

Nick Ryder

Nikhil Srivastava

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

On the Bit Complexity of Sum-of-Squares Proofs.

[BibT_eX]

[DOI]

Benjamin Weitz

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

The Power of Sum-of-Squares for Detecting Hidden Structures.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

The matching problem has no small symmetric SDP.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Correlation Decay and Tractability of CSPs.

[BibT_eX]

[DOI]

Jonah Brown-Cohen

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Combinatorial Optimization Algorithms via Polymorphisms.

[BibT_eX]

[DOI]

Jonah Brown-Cohen

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

Lower Bounds on the Size of Semidefinite Programming Relaxations.

[BibT_eX]

[DOI]

James R. Lee

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

David Witmer

John Wright

Proceedings of the Approximation, 2015

2014

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

On mimicking networks representing minimum terminal cuts.

[BibT_eX]

[DOI]

Arindam Khan

Inf. Process. Lett., 2014

Computational Limits for Matrix Completion.

[BibT_eX]

[DOI]

Proceedings of The 27th Conference on Learning Theory, 2014

On the Power of Symmetric LP and SDP Relaxations.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Gap Amplification for Small-Set Expansion via Random Walks.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Foreword to the Special Issue on SODA'11.

[BibT_eX]

[DOI]

Shuchi Chawla

Dana Randall

ACM Trans. Algorithms, 2013

The Complexity of Approximating Vertex Expansion.

[BibT_eX]

[DOI]

Anand Louis

Santosh S. Vempala

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Approximate Constraint Satisfaction Requires Large LP Relaxations.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

On Mimicking Networks Representing Minimum Terminal Cuts

[BibT_eX]

[DOI]

CoRR, 2012

Many sparse cuts via higher eigenvalues.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Approximating CSPs with global cardinality constraints using SDP hierarchies.

[BibT_eX]

[DOI]

Ning Tan

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Bypassing UGC from some optimal geometric inapproximability results.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Testing odd-cycle-freeness in Boolean functions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Making the Long Code Shorter.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Reductions between Expansion Problems.

[BibT_eX]

[DOI]

Madhur Tulsiani

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Making the long code shorter, with applications to the Unique Games Conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Generic Techniques to Round SDP Relaxations.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Finding Almost-Perfect Graph Bisections.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Rounding Semidefinite Programming Hierarchies via Global Correlation.

[BibT_eX]

[DOI]

Boaz Barak

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Approximations for the isoperimetric and spectral profile of graphs and related parameters.

[BibT_eX]

[DOI]

Prasad Tetali

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Graph expansion and the unique games conjecture.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Approximating Sparsest Cut in Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

Eden Chlamtac

Robert Krauthgamer

Proceedings of the Approximation, 2010

2009

Perfectly reliable and secure message transmission tolerating mobile adversary.

[BibT_eX]

[DOI]

Int. J. Appl. Cryptogr., 2009

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

List decoding tensor products and interleaved codes.

[BibT_eX]

[DOI]

Parikshit Gopalan

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Buffer management for colored packets with deadlines.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

Towards computing the Grothendieck constant.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

How to Round Any CSP.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Agnostic Learning of Monomials by Halfspaces Is Hard.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On the Communication Complexity of Read-Once AC^0 Formulae.

[BibT_eX]

[DOI]

T. S. Jayram

Swastik Kopparty

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Optimal algorithms and inapproximability results for every CSP?

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.

[BibT_eX]

[DOI]

Rajsekar Manokaran

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

A Note on Yekhanin's Locally Decodable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

A 3-query PCP over integers.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Coarse Differentiation and Multi-flows in Planar Graphs.

[BibT_eX]

[DOI]

James R. Lee

Proceedings of the Approximation, 2007

Improved Approximation Algorithms for the Spanning Star Forest Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

On Proactive Perfectly Secure Message Transmission.

[BibT_eX]

[DOI]

Kannan Srinathan

C. Pandu Rangan

Proceedings of the Information Security and Privacy, 12th Australasian Conference, 2007

2006

Hardness of Learning Halfspaces with Noise.

[BibT_eX]

[DOI]