Prasad Raghavendra

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

Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Raghu Meka

SIAM J. Comput., 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

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 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

2017

The matching problem has no small symmetric SDP.

[BibT_eX]

[DOI]

Math. Program., 2017

Dimension Reduction for Polynomials over Gaussian Space and Applications.

[BibT_eX]

[DOI]

Badih Ghazi

Pritish Kamath

Electron. Colloquium Comput. Complex., 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

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

Approximate Constraint Satisfaction Requires Large LP Relaxations.

[BibT_eX]

[DOI]

J. ACM, 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

Making the Long Code Shorter.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Combinatorial Optimization Algorithms via Polymorphisms.

[BibT_eX]

[DOI]

Jonah Brown-Cohen

Electron. Colloquium Comput. Complex., 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

David Witmer

John Wright

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

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

Improved Approximation Algorithms for the Spanning Star Forest Problem.

[BibT_eX]

[DOI]

Algorithmica, 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

2012

Agnostic Learning of Monomials by Halfspaces Is Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

2011

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

List Decoding Tensor Products and Interleaved Codes.

[BibT_eX]

[DOI]

Parikshit Gopalan

SIAM J. Comput., 2011

Buffer Management for Colored Packets with Deadlines.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Testing Odd-Cycle-Freeness in Boolean Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Rounding Semidefinite Programming Hierarchies via Global Correlation.

[BibT_eX]

[DOI]

Boaz Barak

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

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

Reductions Between Expansion Problems.

[BibT_eX]

[DOI]

Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2010

Bypassing UGC from some optimal geometric inapproximability results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Hardness of Learning Halfspaces with Noise.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

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

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

Coarse Differentiation and Multi-flows in Planar Graphs.

[BibT_eX]

[DOI]

James R. Lee

Electron. Colloquium Comput. Complex., 2008

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

On Proactive Perfectly Secure Message Transmission.

[BibT_eX]

[DOI]

Kannan Srinathan