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 $\epsilon$ and…