The Majority Is Stablest Theorem (to be proved at the end of this section) was originally conjectured in 2004 [KKMO04,KKMO07]. The motivation came from studying the approximability of the MaxCut CSP.
[...]


The Majority Is Stablest Theorem (to be proved at the end of this section) was originally conjectured in 2004 [KKMO04,KKMO07]. The motivation came from studying the approximability of the MaxCut CSP. [...] In Theorem 36 we saw that it is $\mathsf{NP}$hard to $(1\delta_0, 1)$approximate MaxE$3$Sat for some positive but inexplicit constant $\delta_0$. You might wonder how large $\delta_0$ can be. The natural limit here is $\frac18$ because there is a very simple algorithm which satisfies a $\frac78$fraction of the constraints in any MaxE$3$Sat instance: [...] 

Copyright © 2015 Ryan O'Donnell  All Rights Reserved 
Recent comments