Alphabet Reduction and the PCP Theorem: Examples and Counterexamples

By [F1] the dimension-one table is evaluated at masks $0$ and $1$, so ${\mathrm{WH}}_1(1)=(1\cdot 0,1\cdot 1)=(0,1)$ with length $\mathrm{\ell }=2^1=2$, in agreement with the code selection of [F2].

The labeling $\sigma (v)=\sigma (w)=1$ is a graph labeling, and its ordered endpoint pair $(1,1)$ lies in $R_e=\{(0,0),(1,1)\}$; since the equality edge is the only edge, ${\mathrm{val}}_{\sigma }(G)=1$ and $\mathrm{val}(G)=1$, so $\mathrm{UNSAT}(G)=0$ by [F3].

The block assigned to both endpoints is $B_v=B_w=C(1)=(0,1)$ by [F2]. Both blocks are valid codewords and decode uniquely to the labels $1,1$, whose ordered pair lies in $R_e$; hence the robust edge circuit accepts the displayed input by [F2].

Since $\mathrm{val}(G)=1$, [F4] gives $\mathrm{val}(H)=1$: some assignment to the variables of $H$ satisfies every constraint of $H$. By [F5], the single edge contributes $M=q_e$ constraints, namely the constraints of the local two-piece tester copied once each; therefore one assignment satisfies every tester gadget constraint simultaneously.

Apply the conversion of [F6] to $H$. The satisfying assignment of step 2.2 extends to a labeling of the output graph that satisfies every output edge, so the output has value one and unsatisfaction zero: the number of violated edges is $0$. The conversion creates at most $6M$ edge records and uses the fixed 66-symbol alphabet $\{B(0),B(1)\}\bigsqcup \{0,1{\}}^6$, so this is a concrete instance of the composition and conversion maps with no random or infinite selection anywhere.

Fix a no input $x$ and any proof $\pi$, and let $p=\mathrm{Pr}[V^{\pi }(x)\text{ accepts}]$. By the soundness premise, $0\le p\le 3\mathrm{/}4$. Applying [F1] with $k=3$ gives repeated acceptance probability $p^3\le (3\mathrm{/}4{)}^3=27\mathrm{/}64$. Since this holds for every fixed proof, the repeated verifier has the claimed soundness.

The three independent runs use at most $3r(n)$ random bits and concatenate at most three query lists of size $q(n)$, so the total is at most $3q(n)$ symbol queries. They all inspect the same proof of length at most $L(n)$, rather than storing three proofs; the combined query locations are fixed by the input and the full random tape, so the repeated verifier remains nonadaptive.

The only vertex labels are $0$ and $1$. Label $0$ passes $e_0$ and fails $e_1$; label $1$ passes $e_1$ and fails $e_0$. Thus every labeling violates exactly one of the two edges and $\mathrm{UNSAT}(G)=1\mathrm{/}2$. Each loop has two incidence slots, so the one-vertex graph is $d=4$ regular.

Set $t=1$, so $R=t+\lceil \sqrt{t}\rceil =2$. In the local-view convention, a powered label assigns an element of $\mathrm{\Sigma }$ to each length-$R$ lazy-step pattern, hence the pattern set has size $(2d{)}^R=8^2=64$ and the view alphabet has size $\mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^{64}=2^{64}$.

Since $2^{64}>2=\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }$, this explicit power does not preserve the alphabet, contradicting the universal assertion in [F1]. The witness uses a positive parameter and has the claimed base unsatisfaction $1\mathrm{/}2$; it makes no claim that every graph or every parameter yields alphabet growth.

Using [F1], the dot products of $u=(1,0)$ on masks $(00,01,10,11)$ are $0,0,1,1$, while those of $v=(0,1)$ are $0,1,0,1$. These are exactly the coordinates of the two stated tables.

The displayed tables disagree at masks $01$ and $10$, and agree at $00$ and $11$. Thus they differ in exactly $2$ of $4$ positions, so their relative distance is $2\mathrm{/}4=1\mathrm{/}2$, also as asserted generally by [F2].

For $f={\mathrm{WH}}_2(u)$, the chosen sample has $x+y=10+01=11$. The table in step 1.1 gives $f(10)=1$, $f(01)=0$, and $f(11)=1$; hence $f(x)+f(y)=1+0=1=f(x+y)$ in ${\mathbb{F}}_2$, so this BLR sample accepts by [F3].

Step 2.2 checks one fixed transcript only. It does not calculate the rejection fraction over all uniform pairs for an arbitrary oracle table, which is the $ϵ$ in [F4]; in particular, this sample alone does not establish the nearby-decoder theorem's global premise. No choice principle is used: all vectors and four masks are explicitly listed.