658 citations · 2.2k across the 187 of their papers we have counts for
Showing 2012 · cs.CCShow all
2 papers · 2 filters
cs.CC2012★ 6 cited
Majority is Stablest : Discrete and SoS
Anindya De, Elchanan Mossel, Joe Neeman
The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof of the Majority is Stablest Theorem by inducti…
cs.CC2012
Explicit Optimal Hardness via Gaussian stability results
Anindya De, Elchanan Mossel
The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program t…