Alphabet Reduction and the PCP Theorem

For the graph-to-verifier direction, order the $m$ edges and use $r_G=\lceil {\log }_{2}m\rceil$ random bits to choose one of $2^{r_G}$ indices. For indices below $m$, query the edge's endpoints in its specified order and accept exactly when their labels satisfy its relation; surplus indices accept without queries. This is nonadaptive, and a loop reads the same proof symbol twice. For a fixed labeling $\sigma$, exactly $m{\mathrm{UNSAT}}_{\sigma }(G)$ of the $m$ real-edge indices reject, so the rejection probability is $m{\mathrm{UNSAT}}_{\sigma }(G)\mathrm{/}{2}^{r_G}$. Since $2^{r_G}<2m$, this is at least half the labeling's unsatisfaction; taking the minimum over labelings gives the stated graph-unsatisfiability bound.

For the verifier-to-graph direction, enumerate its $2^r$ random tapes. On each tape the nonadaptive query addresses are fixed. Make one ordered edge per tape with endpoint vertices equal to the two queried proof positions, and put in its relation exactly the answer pairs on which that tape accepts. If the two addresses coincide, make a loop with relation $\{(a,a):V\text{ accepts on this tape when the repeated location returns }a\}$; its off-diagonal entries are empty. If there is one query, use a fresh dummy vertex as the second endpoint and let the relation ignore its label; if there are no queries, use a loop at a dummy vertex with relation ${\mathrm{\Sigma }}^2$ when that tape accepts and the empty relation when it rejects. Retain parallel edges, including identical tape outcomes, so the graph has exactly $2^r$ edges.

For any fixed proof $\pi$, label each retained proof-position vertex by its symbol and each dummy by a fixed default symbol in the nonempty alphabet. The edge for a tape is satisfied exactly when that run accepts, so its satisfied-edge fraction equals $\mathrm{Pr}[V^{\pi }(x)\text{ accepts}]$. Conversely, any graph labeling extends to a proof by assigning its symbols at retained positions and a fixed default symbol at every unused proof position; hence maximizing over proofs gives exactly $\mathrm{val}(G_{V,x})$. Since the proof space is finite, this maximum is attained.

At most two proof positions occur on each of $2^r$ tapes, so after removing unused proof positions the graph has at most $2^{r+1}+1$ vertices, and its fixed-size relation tables and endpoint names can be written in polynomial time in $\mathrm{\mid }x\mathrm{\mid }+2^r$. Thus $r=O(\log \mathrm{\mid }x\mathrm{\mid })$ gives a polynomial-size graph. The exact value equality in step 2.1, [F3] and [F4] transfer both threshold directions: value at least $c$ iff some fixed proof accepts with probability at least $c$, and value at most $s$ iff every fixed proof accepts with probability at most $s$. For binary proofs, choose $k=\max (1,\lceil {\log }_2\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }\rceil )$ and a fixed surjection $D:\{0,1{\}}^k\to \mathrm{\Sigma }$; decoding each queried block makes every bit proof a $\mathrm{\Sigma }$-symbol proof, and every symbol proof has a block encoding, so the maximum is unchanged while at most $2k=O(1)$ bits are queried.

Put $d=u+v$. Since $u\mathrm{\ne }v$, $d$ is nonzero. At a mask $r\in {\mathbb{F}}_2^n$, the two table values disagree exactly when $(u\cdot r)+(v\cdot r)=d\cdot r=1$.

Choose a coordinate $j$ with $d_j=1$ and let $e_j$ be its unit vector. The map $r\mapsto r+e_j$ is an involution without fixed points, and $d\cdot (r+e_j)=d\cdot r+1$. Thus it partitions the $2^n$ masks into $2^{n-1}$ pairs, with exactly one mask in each pair satisfying $d\cdot r=1$. The coordinate choice exists because $d$ is a nonzero finite binary vector.

By step 2.1 and the disagreement criterion in step 1.1, exactly $2^{n-1}$ table coordinates differ. Dividing by the $2^n$ coordinates gives relative distance $2^{n-1}\mathrm{/}{2}^n=1\mathrm{/}2$. If $n=0$, ${\mathbb{F}}_2^0$ has only its empty vector, so the statement has no distinct-message pair to check.

For each block $B_v$, the fixed alphabet order makes its nearest valid codeword label $a_v$ deterministic; a minimizer exists because $\mathrm{\Sigma }$ is finite and nonempty. For every $a^{\mathrm{\prime }}\mathrm{\ne }{a}_v$, nearestness and the triangle inequality give $\delta \mathrm{\ell }\le d_H(C(a_v),C(a^{\mathrm{\prime }}))\le d_H(C(a_v),B_v)+d_H(B_v,C(a^{\mathrm{\prime }}))\le 2d_H(B_v,C(a^{\mathrm{\prime }}))$. Hence every changed decoded label has $d_H(B_v,C(a^{\mathrm{\prime }}))\ge \delta \mathrm{\ell }\mathrm{/}2=\mathrm{\ell }\mathrm{/}4$.

Suppose $(a_v,a_w)\mathrm{\notin }{R}_e$. By [F2], every accepting formal input $(X,Y)$ is $(C(a^{\mathrm{\prime }}),C(b^{\mathrm{\prime }}))$ for some $(a^{\mathrm{\prime }},b^{\mathrm{\prime }})\in R_e$, so at least one decoded endpoint changes. By step 1.1, the corresponding formal block differs from the actual block by at least $\mathrm{\ell }\mathrm{/}4$ bits; division by the $2\mathrm{\ell }$ formal input bits gives relative distance at least $\delta \mathrm{/}4=1\mathrm{/}8$. If $v=w$, the actual formal pair is $(B_v,B_v)$ and the violated loop pair is $(a_v,a_v)\mathrm{\notin }{R}_e$, so every accepting pair still changes at least one of the two decoded labels and the same bound applies to that formal block. If there are no accepting inputs, [F3] sets the distance to $1\ge 1\mathrm{/}8$.

Since $d\mathrm{\ne }0$, choose the least index $j$ with $d_j=1$, and let $e_j$ be its unit vector. The map $z\mapsto z+e_j$ is a fixed-point-free involution of the cube and $(z+e_j)\cdot d=z\cdot d+1$, so it pairs each outcome with one whose dot product has the opposite bit.

Each pair from step 1.1 has exactly one vector with $z\cdot d=1$, hence exactly $2^{m-1}$ of the $2^m$ vectors satisfy the event and its uniform probability is $1\mathrm{/}2$. Equivalently these are precisely the coordinates where ${\mathrm{WH}}_m(0)$ and ${\mathrm{WH}}_m(d)$ disagree, consistent with the half-distance lemma in [F1]. Thus every nonzero violated-equation vector and every difference of distinct prefixes has the same detection probability; the number and correlations of its coordinates are irrelevant.

Number the $s$ primary input wires first, then number the $m$ remaining nodes in topological order, and associate a variable $w_i$ to each wire. Thus $N=s+m$, and fixing $w_1,\dots ,w_n$ to $x$ fixes exactly the named prefix; the other primary input variables remain available for the completion.

For a constant node with variable $z$ and value $c$, impose $z=c$; for a NOT node with input $a$ impose $z+a=1$; for an AND node with inputs $a,b$ impose $z+ab=0$; and for an OR node impose $z+a+b+ab=0$. These equations force exactly the indicated Boolean operation: in particular $a\vee b=a+b+ab$ for bits. They remain valid when the two input wires coincide, after reducing repeated monomials using $a^2=a$ in ${\mathbb{F}}_2$. Append the output equation $w_{\mathrm{o}\mathrm{u}\mathrm{t}}=1$. There are $m+1$ equations, each with at most four monomials. Using [F1], place each linear term on its diagonal tensor coordinate, each quadratic term on its upper-triangular coordinate, and each constant on the right-hand side; this gives a canonical QUADEQ instance.

Suppose a solution extends the prefix $x$. Its next $s-n$ coordinates define a completion $y$. The gate equations in step 2.1, read in topological order, force every non-input wire to equal its evaluated circuit value, and the output equation forces $C(x,y)=1$.

Conversely, suppose some completion $y$ makes $C(x,y)=1$. Set the first $s$ variables to $(x,y)$ and set every remaining variable to the value of its node under the circuit evaluation. Each constant or gate equation in step 2.1 then holds by its defining Boolean operation, and the output equation holds because the output is one. This constructs a QUADEQ solution extending $x$, proving the reverse implication.

The construction lists one constant-size equation per node and one output equation. Writing each of the $m+1$ coefficient matrices with $N^2$ entries takes $O((m+1)N^2)$ time; since the explicit description lists all $s+m=N$ wires, this is polynomial in its length. The equations themselves have the claimed bound from step 2.1. The construction uses only the topological order and fixed gate formulas, so it is deterministic.

The BLR test accepts exactly when $f(x)+f(y)+f(x+y)=0$ in ${\mathbb{F}}_2$. Thus $h(x)h(y)h(x+y)$ is $1$ on acceptance and $-1$ on rejection, so ${\mathbb{E}}_{x,y}[h(x)h(y)h(x+y)]=1-2ϵ$. For $n=0$ the only pair is $((),())$ and the test rejects exactly when $f(())=1$, so $ϵ<1\mathrm{/}2$ forces $f(())=0$.

Write ${\chi }_a(x)=(-1{)}^{a\cdot x}$. By Fourier inversion (F2), $h(x+y)={\sum }_a\widehat{h}(a){\chi }_a(x+y)$, and ${\chi }_a(x+y)={\chi }_a(x){\chi }_a(y)$. Expanding the expectation in step 1.1 and using independence of $x,y$ gives ${\mathbb{E}}_{x,y}[h(x)h(y)h(x+y)]={\sum }_a\widehat{h}(a)({\mathbb{E}}_{x}h(x){\chi }_a(x))({\mathbb{E}}_{y}h(y){\chi }_a(y))={\sum }_a\widehat{h}(a{)}^3$.

Parseval (F3) and $h^2=1$ give ${\sum }_a\widehat{h}(a{)}^2=1$. With $M={\max }_a\widehat{h}(a)$, step 2.1 yields $1-2ϵ={\sum }_a\widehat{h}(a{)}^3\le M{\sum }_a\widehat{h}(a{)}^2=M$. Choose the first maximizer $a_{\ast }$ in the finite lexicographic order. Since $\widehat{h}(a_{\ast })=\mathrm{Pr}[f(x)=a_{\ast }\cdot x]-\mathrm{Pr}[f(x)\mathrm{\ne }{a}_{\ast }\cdot x]$, its Walsh–Hadamard word has distance $(1-\widehat{h}(a_{\ast }))\mathrm{/}2\le ϵ$.

If $ϵ<1\mathrm{/}4$, the word from step 3.1 is within distance $<1\mathrm{/}4$. Any other linear word within distance $<1\mathrm{/}4$ would, by the triangle inequality for normalized Hamming distance, be at distance $<1\mathrm{/}2$ from it, contradicting (F4); for $n=0$ there is only one linear word. Thus the nearby word is unique.

By (F5), the corrector returns $f(y)+f(r+y)$. Each point $y$ and $r+y$ is uniform, so each queried value differs from $a_{\ast }\cdot y$ or $a_{\ast }\cdot (r+y)$ with probability $\delta =\mathrm{dist}(f,{\mathrm{WH}}_n(a_{\ast }))\le ϵ$. A union bound, without assuming independence of the two error events, shows that with probability at least $1-2ϵ$ both values are correct; then their sum is $a_{\ast }\cdot r$. When $n=0$, $ϵ<1\mathrm{/}2$ forces $f(())=0$, and the singleton-table corrector returns the sole linear value $0$.

Let $D=V+u\otimes u\mathrm{\ne }0$ over ${\mathbb{F}}_2$, choose the first nonzero column $j$ of $D$, and view $r$ as a row vector. By [F4], $rD\mathrm{\ne }0$ with probability at least $\mathrm{Pr}[r\cdot D_{\ast ,j}=1]=1\mathrm{/}2$. For each such $r$, $rD$ is a nonzero vector, so [F4] gives ${\mathrm{Pr}}_s[rDs=1]=1\mathrm{/}2$. Since $G_V(r\otimes s)+F_u(r)F_u(s)=rDs$ by [F1] and [F3], the rejection probability of the ideal test in [F2] is at least $1\mathrm{/}4$.

For any fixed requested point $q$ and any fixed table $h$ at relative distance $\eta$ from a linear form $L$, the points $a$ and $q+a$ are both uniform when $a$ is uniform. Unless either lies in the error set, [F5] returns $h(a)+h(q+a)=L(a)+L(q+a)=L(q)$. The union bound therefore gives corrector error at most $2\eta$, uniformly in $q$, including $q=0$.

Apply step 1.2 to the two requests $r,s$ for $f$ and to request $r\otimes s$ for $g$. The probability that any of the three corrected values is wrong is at most $2{\delta }_f+2{\delta }_f+2{\delta }_g=4{\delta }_f+2{\delta }_g$. Outside that union, the self-corrected predicate in [F6] equals the ideal predicate in [F2]. Hence its rejection probability is at least the ideal rejection probability from step 1.1 minus $4{\delta }_f+2{\delta }_g$, which is the claimed bound; no independence of the correction errors is used.

The test samples $r,s,y,y^{\mathrm{\prime }}$ using $4N$ unbiased bits and $Y$ using $N^2$ more, computes all six query locations before receiving any table value, and makes exactly six queries as stated in [F6]. Repeated locations are permitted by [F5]; for $N=0$, all domains are singletons and the hypothesis is impossible.

Put $d_j=A_j\cdot (u\otimes u)+b_j$. Since $u$ fails at least one equation, $d\mathrm{\ne }0$. Linearity gives $A(z)\cdot (u\otimes u)+b(z)=z\cdot d$, so the combined equation fails exactly when $z\cdot d=1$; by [F3] this occurs with probability exactly $1\mathrm{/}2$.

Fix any requested tensor coordinate $q$. Let $E=\{y:g(y)\mathrm{\ne }G(y)\}$, so $\mathrm{\mid }E\mathrm{\mid }\mathrm{/}{2}^{N^2}=\delta$. Both $y$ and $q+y$ are uniform, and by [F4] the corrector returns $g(y)+g(q+y)$. Unless one of these two points lies in $E$, this equals $G(y)+G(q+y)=G(q)$ by linearity of the intended oracle in [F2]; a union bound therefore gives correction failure probability at most $2\delta$, uniformly for every $q$, including $q=0$.

For the test, condition on each $z$ and set $q=A(z)$. By [F2] and [F1], on the event from step 1.1 the ideal value $G(q)=A(z)\cdot (u\otimes u)$ differs from $b(z)$; whenever the correction in step 1.2 returns $G(q)$, the test rejects. Its failure probability conditional on each $z$ is at most $2\delta$, so averaging gives $\mathrm{Pr}[\text{reject}]\ge \mathrm{Pr}[z\cdot d=1]-2\delta =\frac{1}{2}-2\delta$, without any independence assumption between rejection and correction errors.

The test samples $M$ bits for $z$ and $N^2$ bits for $y$, computes both query locations before reading $g$, and makes exactly two symbol queries; thus it is nonadaptive and uses one combined equation instead of querying all $M$ original equations. If $M=0$, its premise is impossible; if $N=0$, the tensor domain is a singleton and the corrector queries that same coordinate twice, as allowed by [F4].

First replace each input matrix $A_j$ by its canonical upper-triangular representative: keep its diagonal entries, put $A_{j,ik}+A_{j,ki}$ in position $(i,k)$ for $i<k$, and put zero below the diagonal. By [F1] this preserves every value $A_j\cdot (u\otimes u)$ and therefore the solution set; scanning the explicit matrices costs $O(M{N}^2)$ time. In the rest of the proof $A_j$ denotes this canonical representative, so [F8] applies. Split the proof, using [F3], into fixed tables $f:{\mathbb{F}}_2^N\to {\mathbb{F}}_2$ and $g:{\mathbb{F}}_2^{N^2}\to {\mathbb{F}}_2$. Unless $N=M=0$, use two selector bits to choose uniformly among one BLR test on $f$, one BLR test on $g$, the six-query tensor test in [F7], and the two-query equation test in [F8]; all test coins are independent and their query locations are computed before reading answers.