87 citations · 305 across the 39 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016
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…
cs.CC2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
We prove that with high probability over the choice of a random graph from the Erdős-Rényi distribution , the -time degree Sum-of-Squares semidefinite p…