38 citations · 171 across the 26 of their papers we have counts for
18 papers · 1 filter
Extended Formulation Lower Bounds for Refuting Random CSPs
Jonah Brown-Cohen, Prasad Raghavendra
Random constraint satisfaction problems (CSPs) such as random -SAT are conjectured to be computationally intractable. The average case hardness of random -SAT and other CSPs…
Lifting Sum-of-Squares Lower Bounds: Degree- to Degree-
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
The degree- Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, S…
Dimension Reduction for Polynomials over Gaussian Space and Applications
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
We introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure,…
On the Bit Complexity of Sum-of-Squares Proofs
Prasad Raghavendra, Benjamin Weitz
It has often been claimed in recent papers that one can find a degree d Sum-of-Squares proof if one exists via the Ellipsoid algorithm. In [O17], Ryan O'Donnell notes this widely q…
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as -rounds of the Sherali-Adams linear progr…
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Pasin Manurangsi, Prasad Raghavendra
A -birthday repetition of a two-prover game is a game in which the two provers are sent random sets of questions from $\mathc…