Chapter 7 notes

The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of error-correcting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as in Exercise 8); it was later rediscovered by Parnas, Ron, and Samorodnitsky [PRS01,PRS02]. The relevance of Arrow’s Theorem to testing dictatorship was pointed out by Kalai [Kal02].

The idea of assisting testers by providing proofs grew out of complexity-theoretic research on interactive proofs and PCPs; see the early work Ergun, Kumar, and Rubinfeld [EKR99] and the references therein. The specific definition of PCPPs was introduced independently by Ben-Sasson–Goldreich–Harsha–Sudan–Vadhan [BGH+04] and by Dinur–Reingold [DR04] in 2004. Both of these works obtained the PCPP Theorem, relying on the fact that previous literature essentially already gave PCPP reductions of exponential (or greater) proof length): [BGH+04] observed that Theorem 20 can be obtained from [ALM+98] (their proof is Exercise 18), while [DR04] pointed out that the slightly easier Theorem 19 can be extracted from [BGS98]. The proof we gave for Theorem 16 is inspired by the presentation in [Din07].

The PCP Theorem and its stronger forms (the PCPP Theorem and Theorem 21) have a somewhat remarkable consequence. Suppose a researcher claims to prove a famous mathematical conjecture, say “$\mathsf{P} \neq \mathsf{NP}$”. To ensure maximum confidence in correctness, a journal might request the researcher submit a formalized proof, suitable for a mechanical proof-checking system. If the submitted formalized proof $w$ is a boolean string of length $n$, the proof-checker will be implementable by a circuit $C$ of size $O(n)$. Notice that the string property $\mathcal{C}$ decided by $C$ is nonempty if and only if there exists a (length-$n$) proof of $\mathsf{P} \neq \mathsf{NP}$. Suppose the journal applies Theorem 21 to $C$ and requires the researcher submit the additional proof $\Pi$ of length $n \cdot \mathrm{polylog}(n)$. Now the journal can run a rather amazing testing algorithm which reads just $3$ bits of the submitted proof $(w,\Pi)$. If the researcher’s proof of $\mathsf{P} \neq \mathsf{NP}$ is correct then the test will accept with probability $1$. On the other hand, if the test accepts with probability at least $1-\gamma$ (where $\gamma$ is the rejection rate in Theorem 21) then $w$ must be $1$-close to the set of strings accepted by $C$. This doesn’t necessarily mean that $w$ is a correct proof of $\mathsf{P} \neq \mathsf{NP}$ — but it does mean that $\mathcal{C}$ is nonempty and hence a correct proof of $\mathsf{P} \neq \mathsf{NP}$ exists! By querying a larger constant number of bits from $(w,\Pi)$ as in Exercise 1, say $\lceil 30/\gamma\rceil$ bits, the journal can become $99.99$% convinced that indeed $\mathsf{P} \neq \mathsf{NP}$.

CSPs are very widely studied in computer science; it is impossible to survey the topic here. In the case of boolean CSPs the monographs [CKS01,KSTW01] contain useful background regarding complexity theory and approximation algorithms. The notion of approximation algorithms and the derandomized $(\frac78,1)$-approximation algorithm for Max-E$3$-Sat (Proposition 37, Exercise 21) are due to Johnson [Joh74]. Incidentally, there is also an efficient $(\frac78,1)$-approximation algorithm for Max-$3$-Sat [KZ97] but both the algorithm and its analysis are extremely difficult, the latter requiring computer assistance [Zwi02]. Håstad’s hardness theorems are from [Has01], building on [Has96,Has99]. That paper also proves $\mathsf{NP}$-hardness of $(\frac1p + \delta, 1-\delta)$-approximating Max-E$3$-Lin(mod $p$) (for $p$ prime) and of $(\frac78, 1)$-approximating Max-$\mathrm{CSP}(\{\mathrm{NAE}_4\})$, both of which are optimal. Using tools from [TSSW00], Håstad\xspace also showed $\mathsf{NP}$-hardness of $(\frac{11}{16} + \delta, \frac34)$-approximating Max-Cut which is still the best known such result. The best known inapproximability result for Unique-Games($q$) is $\mathsf{NP}$-hardness of $(\frac38 + q^{-\Theta(1)}, \tfrac{1}{2})$-approximation [OW12]. Khot’s influential Unique Games Conjecture was made in [Kho02]; the peculiar name has its origins in a work of Feige and Lov{á}sz [FL92]. The generic Theorem 41, giving UG-hardness from Dictator-vs.-No-Notables tests, essentially appears in [KKMO07]. (We remark that the terminology “Dictator-vs.-No-Notables” is not standard.) If one is willing to assume the Unique Games Conjecture, there is an almost-complete theory of optimal inapproximability due to Raghavendra [Rag09] which will be discussed further in Chapter 14. Many more inapproximability results, with and without the Unique Games Conjecture, are known; for some recent surveys, see [Kho05,Kho10a,Kho10].

As mentioned, Exercise 8 is due to [BGS95,PRS01]. The technique described in Exercise 21 is known as the Method of Conditional Expectations. The trick in Exercise 23 is closely related to the notion of “folding” from the theory of PCPs. The bug described in Exercise 31 is rarely addressed in the literature; the trick used to overcome it appears in, e.g., [ABH+05].

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>