[...]


[...] 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: [...] This section is about the computational complexity of constraint satisfaction problems (CSPs), a fertile area of application for analysis of boolean functions. To study it we need to introduce a fair bit of background material; in fact, this section will mainly consist of definitions. [...] 

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