In Theorem 36 we saw that it is $\mathsf{NP}$-hard to $(1-\delta_0, 1)$-approximate Max-E$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 Max-E$3$Sat instance:

[...]

## Recent comments

Matt Franklin: Maybe two small typos in the proof of Corollary 11.67 (p. 36...Ryan O'Donnell: I see your point, although in some sense this distinction be...Ryan O'Donnell: Thank you!Ryan O'Donnell: Yep, thanks!Ryan O'Donnell: Great catch, thanks!Matt Franklin: Maybe two small typos in last sentence before Borell's Isope...Matt Franklin: maybe small typo in Remark 11.11 (p. 328 in book): $z \tild...