A two-piece constant-query PCP of proximity

Deterministically reorder the primary input list as $X_1\mathrm{\parallel }{X}_2\mathrm{\parallel }(\text{remaining inputs})$; this relabeling preserves circuit evaluation. Apply [F1] with named prefix length $n=n_1+n_2$, obtaining a QUADEQ instance with $N=s+m$ variables and $M=m+1$ equations. Its first $n_1$ variables are $X_1$, and the next $n_2$ are $X_2$, so the coordinate injections are $j_1(r)=(r,0^{N-n_1})$ and $j_2(r)=(0^{n_1},r,0^{N-n})$. The two designated slices are disjoint and have the prescribed order.

Split the fixed proof into external tables ${\pi }_1,{\pi }_2$ and private tables $F,G$ of lengths $2^{n_1},2^{n_2},2^N,2^{N^2}$. Choose uniformly among eight families: BLR on each table, the six-query tensor test, the two-query equation test, and the four-query corrected slice test for each $j_i$. Each family samples only its own independent uniform coins, and every query location is computed before any answer is read.

If $(a_1,a_2)$ is satisfying, choose a completion of the other input wires on which $C$ outputs one. By [F1] it gives a QUADEQ solution $w$. Set ${\pi }_i={\mathrm{WH}}_{n_i}(a_i)$, $F={\mathrm{WH}}_N(w)$, and $G={\mathrm{WH}}_{N^2}(w\otimes w)$. Every BLR family accepts because its table is linear. The tensor family accepts since $(w\cdot r)(w\cdot s)=(w\otimes w)\cdot (r\otimes s)$, and each equation family accepts since $w$ solves every equation. The named slices of $w$ are $a_i$, so the corrected slice tests compare equal linear values on every tape. If $n_i=0$, both requests are zero and both corrected values are zero. Thus all eight families accept on every tape.

The branch coin counts are $2n_1,2n_2,2N,2N^2,4N+N^2,M+N^2,2n_1+N,2n_2+N$; three selector bits choose the branch. Since $n_i\le N$, $M=m+1\le N+1$, and $N\ge 1$, every branch uses at most $5N^2$ bits, so the verifier uses at most $3+5N^2$ bits and at most six queries. Its proof length is the sum of the four table lengths in step 1.2 and is at most $4\cdot 2^{N^2}$ because $n_i\le N\le N^2$. The circuit reduction, sample addresses, tensor products, and equation subsums are computable in time polynomial in the explicit circuit description, giving a deterministic uniform construction.

For an arbitrary fixed proof, let ${ϵ}_j$ be the rejection probability of each of the eight families and $R=\frac{1}{8}{\sum }_{j=1}^8{ϵ}_j$ the verifier's rejection probability. If $R<1\mathrm{/}800$, then every ${ϵ}_j\le 8R<1\mathrm{/}100$. By [F5] the four BLR tables have deterministically selected unique decoders $a_i\in {\mathbb{F}}_2^{n_i}$, $w\in {\mathbb{F}}_2^N$, and $v\in {\mathbb{F}}_2^{N^2}$, each at distance at most its BLR rejection rate and therefore below $1\mathrm{/}100$. Denote these distances by ${\delta }_{{\pi }_1},{\delta }_{{\pi }_2},{\delta }_F,{\delta }_G$, and reshape $v$ in row-major order as a matrix $V$.

Make variables from the raw named input bits and every coordinate of ${\pi }_1,{\pi }_2,F,G$. For each random tape in each core family, list the ordered tuple of queried table variables with the Boolean relation that accepts exactly the answers accepted by that test. The relations are explicit: BLR accepts $b_1+b_2=b_3$; the tensor test accepts $q_1+q_2=(p_1+p_2)(p_3+p_4)$ on ordered answers $p_1,p_2,p_3,p_4,q_1,q_2$; the equation test accepts when the queried sum equals its fixed $b(z)$; and a slice test accepts when its corrected sums agree. Repeated query locations yield repeated variables, allowed by [F13]. If $n>0$, add comparisons indexed by each named coordinate $i$ and each $t\in {\mathbb{F}}_2^L$, $L=\max (n_1,n_2)$: take the first $n_i$ coordinates of $t$ as $y$ in the piece containing $i$, and use the tuple $(x_i,{\pi }_i(y),{\pi }_i(y+e_i))$ with relation $x_i={\pi }_i(y)+{\pi }_i(y+e_i)$ from [F12]. This comparison has arity three.

If $V\mathrm{\ne }w\otimes w$, [F6] gives tensor-family rejection at least $\frac{1}{4}-4{\delta }_F-2{\delta }_G>\frac{1}{4}-\frac{6}{100}=\frac{19}{100}$, hence $R>19\mathrm{/}800>1\mathrm{/}800$, a contradiction. Thus $V=w\otimes w$. If $w$ failed any QUADEQ equation, [F7] gives equation-family rejection at least $\frac{1}{2}-2{\delta }_G>\frac{48}{100}$ and hence $R>48\mathrm{/}800>1\mathrm{/}800$, also impossible. Thus $w$ solves the reduced instance.

Let $K$ be the maximum coin count of a core family and $D=n{2}^L$ when $n>0$. The comparison list has $D$ constraints, and each core family has $2^{c_j}$ tapes with $c_j\le K$. For $n>0$, duplicate rows until each of the nine families has $P=D{2}^K$ constraints; $P\mathrm{/}{2}^{c_j}$ and $P\mathrm{/}D$ are integers. For $n=0$, omit comparisons and duplicate the eight core families to $P=2^K$ constraints each. Therefore the violated fraction is the average of the core-family rejection rates and, when present, the comparison rejection rate. If $n>0$, $D=n{2}^L$ and $L\le n\le N$ imply ${\log }_{2}D\le {\log }_{2}n+L\le 2N^2$; step 2.1 gives $K\le 5N^2$. Hence $P\le 2^{7N^2}$ and there are at most $9\cdot 2^{7N^2}\le 2^{7N^2+4}$ constraints. If $n=0$, there are at most $8\cdot 2^{5N^2}\le 2^{7N^2+4}$. Direct enumeration takes time polynomial in the output length.

If $x$ is accepted by $C$, use the satisfying completion and exact tables from step 1.3 as the auxiliary labeling. Every core constraint accepts. For each named coordinate $i$, ${\pi }_i(y)+{\pi }_i(y+e_i)=a_i\cdot e_i=x_i$ for every $y$ by [F3, F12], so every comparison accepts and the tester has perfect completeness.

If either decoded external word $a_i$ differed from the corresponding slice of $w$, [F8] gives that slice family's rejection at least $\frac{1}{2}-2{\delta }_{{\pi }_i}-2{\delta }_F>\frac{1}{2}-\frac{4}{100}=\frac{46}{100}$, hence $R>46\mathrm{/}800>1\mathrm{/}800$, impossible. Each $a_i$ therefore equals its designated slice. By [F1] the pair is satisfying, and by [F5] $\mathrm{dist}({\pi }_i,{\mathrm{WH}}_{n_i}(a_i))<1\mathrm{/}100$ for each $i$. This proves proximity soundness with $\eta =1\mathrm{/}800$ and ${\delta }_0=1\mathrm{/}100$; if no satisfying pair exists, every fixed proof has rejection at least $1\mathrm{/}800$.

Suppose $n>0$, fix any raw named input $x$ and any auxiliary labeling, and let $R$ be the rejection rate of its eight core families. If $R\ge 1\mathrm{/}800$, the nine-family system rejects at least $\frac{8}{9}R\ge \frac{1}{900}>\frac{1}{1000}\delta (x,\mathrm{SAT}(C))$, since the defined distance is at most one by [F15]. Otherwise step 4.1 supplies a satisfying pair $a$ with each external table at distance below $1\mathrm{/}100$ from its Walsh–Hadamard word. Put $d=\mathrm{\mid }\{i:x_i\mathrm{\ne }{a}_i\}\mathrm{\mid }\mathrm{/}n$. For a mismatched coordinate, the two queried locations $y,y+e_i$ are each uniform in their piece's mask space, so each hits a table-error position with probability ${\delta }_{{\pi }_i}<1\mathrm{/}100$. By [F3, F12] and a union bound, the corrector at $e_i$ returns $a_i$ with probability greater than $1-2\mathrm{/}100=49\mathrm{/}50$, and the comparison-family rejection is at least $(49\mathrm{/}50)d$. The full system rejects with probability at least $(49\mathrm{/}450)d\ge (1\mathrm{/}1000)\delta (x,\mathrm{SAT}(C))$, since $d\ge \delta (x,\mathrm{SAT}(C))$. If the accepted set is empty, the low-$R$ case is impossible by step 4.1, so the high-$R$ case proves soundness using [F15]. For $n=1$, the unique named coordinate receives equal weight across its $2^L$ tapes, so the same estimate holds.

If $n=0$, there is one raw named input. If $C$ accepts it, the distance to the accepted set is zero. Otherwise the accepted set is empty by [F15], and step 4.1 implies every proof tuple has core rejection at least $1\mathrm{/}800$; the eight-family system therefore has violated fraction at least $1\mathrm{/}800>1\mathrm{/}1000$. A piece with $n_i=0$ contributes no comparison coordinates; its table domain is a singleton and its corrected value at zero is zero, as in step 1.3. A valid circuit has $N\ge 1$ because it has a designated output wire, so no separate $N=0$ verifier case is needed.

The eight-family verifier satisfies the claimed proximity completeness, soundness, query, proof-length, and randomness bounds; the finite constraint construction has the named variables, explicit Boolean relations, arity at most six, perfect completeness, and rejection-ratio inequality for every named input and auxiliary labeling. This proves both assertions.