38 citations · 171 across the 26 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013
Gap Amplification for Small-Set Expansion via Random Walks
Prasad Raghavendra, Tselil Schramm
In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness and…
cs.CC2013
Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu On Chan, James R. Lee, Prasad Raghavendra +1
We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems…
cs.CC2013
The Complexity of Approximating Vertex Expansion
Anand Louis, Prasad Raghavendra, Santosh Vempala
We study the complexity of approximating the vertex expansion of graphs , defined as \[ Φ^V := \min_{S \subset V} n \cdot \frac{|N(S)|}{|S| |V \backslash S|}. \] We give…