An exponential-length constant-query PCP for quadratic equations

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.

If $u$ satisfies the instance, use the proof $f={\mathrm{WH}}_N(u)$ and $g={\mathrm{WH}}_{N^2}(u\otimes u)$. By [F4], both tables are linear, so their BLR tests always pass. For any auxiliary point $a$, $f(a)+f(a+r)=u\cdot a+u\cdot (a+r)=u\cdot r$, and similarly $g(Y)+g(Y+Z)=(u\otimes u)\cdot Z$. Hence the tensor test passes because $(u\cdot r)(u\cdot s)=(u\otimes u)\cdot (r\otimes s)$. Also $g(y)+g(y+A(z))=g(A(z))=A(z)\cdot (u\otimes u)=b(z)$ for every equation mask $z$, so the equation test passes. If $N=M=0$, this proof has $f=0$ and the deterministic dimension-zero BLR test accepts by [F2,F4].

For an arbitrary fixed proof, let ${ϵ}_f$ and ${ϵ}_g$ be the rejection probabilities of its two BLR tests in [F5]. If either is at least $1\mathrm{/}100$, its selected branch contributes at least $(1\mathrm{/}4)(1\mathrm{/}100)=1\mathrm{/}400$ to the mixture's rejection probability.

Otherwise both ${ϵ}_f,{ϵ}_g<1\mathrm{/}100<1\mathrm{/}4$. By [F6], the lemma's lexicographically first decoders are unique linear words $u\in {\mathbb{F}}_2^N$ and $w\in {\mathbb{F}}_2^{N^2}$ at distances ${\delta }_f\le {ϵ}_f<1\mathrm{/}100$ and ${\delta }_g\le {ϵ}_g<1\mathrm{/}100$. Reshape $w$ into the row-major matrix $V$.

Each selected branch uses respectively $2N$, $2N^2$, $4N+N^2$, or $M+N^2$ random bits and at most $3$, $3$, $6$, or $2$ queries. Thus for $N^2+M>0$ the verifier uses at most $2+\max (2N,2N^2,4N+N^2,M+N^2)\le 7(N^2+M)$ random bits and at most six queries. If $N=M=0$, the empty equation list is satisfiable by [F2]; run the deterministic dimension-zero BLR test on $f$ without selector bits, preserving completeness and using three queries.

If $V\mathrm{\ne }u\otimes u$, [F7] makes the tensor branch reject with probability at least $\frac{1}{4}-4{\delta }_f-2{\delta }_g>\frac{1}{4}-\frac{6}{100}=\frac{19}{100}$. Since this branch is chosen with probability $1\mathrm{/}4$, the mixture rejects with probability greater than $19\mathrm{/}400$, hence at least $1\mathrm{/}400$.

If $V=u\otimes u$, unsatisfiability and [F1] imply that the decoded $u$ violates at least one equation. The equation branch then rejects with probability at least $\frac{1}{2}-2{\delta }_g>\frac{1}{2}-\frac{2}{100}=\frac{48}{100}$. With one equation the random mask detects its failed residual with probability $1\mathrm{/}2$; with $N=0$, the unique decoded vector is empty and the same test detects any right-hand side $b(z)=1$. Its mixture contribution is greater than $12\mathrm{/}100$, so again the verifier rejects with probability at least $1\mathrm{/}400$. Coincident query locations are still counted among the at most six calls.

Under the stated encoding, the instance length is at least $N+M+M{N}^2$. Computing the selected test's addresses, tensor products, and XOR-sums $A(z),b(z)$ takes polynomial time in that length; every query address is fixed from the input and random tape before an answer is read. The proof length is exactly $2^N+2^{N^2}$ by [F3], while only the selected branch's at most six bits are read. The verifier is therefore uniform and nonadaptive with the claimed resources.