An exponential-size constant-query base assignment tester

Apply the construction of [F1] to $(C,X)$, obtaining the wire variables $w_1,\dots ,w_N$ with the $n$ named input coordinates first, followed by the other $s-n$ input coordinates, the coefficient vectors $A_k$ and right sides $b_k$ for $k=1,\dots ,M_0$, and the exact extension equivalence. The output system of this step has the variables $f(z)(z\in {\mathbb{F}}_2^N),g(Z)(Z\in {\mathbb{F}}_2^{N\times N}),x_1,\dots ,x_n,$ that is, one variable for every table coordinate of the two Hadamard tables together with the $n$ named input coordinates of the circuit; the intended labeling is $f={\mathrm{\ell }}_w$, $g={\mathrm{\ell }}_{w\otimes w}$, $x_i$ the $i$-th input bit, for the evaluation vector $w$ of an accepted input.

List the following five families of constraints on the variables of step 1.1, each constraint being the tuple of the variables displayed together with the fixed binary relation displayed, where sums are in ${\mathbb{F}}_2$, $e_i$ is the $i$-th unit vector, and $r,s,y,y^{\mathrm{\prime }}\in {\mathbb{F}}_2^N$, $Y,Z,W\in {\mathbb{F}}_2^{N\times N}$, $z\in {\mathbb{F}}_2^{M_0}$, $i\in [n]$ range over all choices:

Perfect completeness. Let $x\in \mathrm{SAT}(C)$ and choose a completion of the named inputs witnessing acceptance and let $w$ be its evaluation vector from [F1], with first $n$ coordinates $x$. Label $f={\mathrm{\ell }}_w$, $g={\mathrm{\ell }}_{w\otimes w}$ and $x_i$ by the corresponding bit, so that ${\mathrm{Corr}}_f$ and ${\mathrm{Corr}}_g$ return the linear values at every point. Every $({\mathrm{L}}_f)$ and $({\mathrm{L}}_g)$ constraint is satisfied because linear functions satisfy the BLR equation, every $(\mathrm{T})$ constraint is satisfied by the perfect completeness of the tensor test, every $(\mathrm{S})$ constraint is satisfied because $A(z)\odot (w\otimes w)={\sum }_k{z}_k(A_k\odot (w\otimes w))={\sum }_k{z}_k{b}_k=b(z)$ as $w$ solves every equation of [F1], and every $(\mathrm{C})$ constraint is satisfied because ${\mathrm{Corr}}_f(e_i)={\mathrm{\ell }}_w(e_i)=w_i=x_i$. Hence ${\mathrm{UNSAT}}_{x\cup b}(P(C,X))=0$ for that labeling.

First soundness case: suppose the table $f$ of a labeling $b$ is at distance more than ${\epsilon }_0=1\mathrm{/}100$ from every linear function. Then the fraction of violated $({\mathrm{L}}_f)$ constraints is the BLR rejection probability of $f$, which by [F2] is at least that distance, hence exceeds ${\epsilon }_0$; after duplication this is still the violated fraction of the family. Since the total is at most $5L$, the system as a whole violates at least ${\epsilon }_{0}L\mathrm{/}(5L)={\epsilon }_0\mathrm{/}5=\rho$ of its constraints, and $\rho \ge \rho \delta (x,\mathrm{SAT}(C))$ because $\delta \le 1$. The same argument applies to the table $g$ and the family $({\mathrm{L}}_g)$.

Second soundness case: suppose both tables are at distance at most ${\epsilon }_0$ from linear functions, say $f$ from ${\mathrm{\ell }}_u$ and $g$ from ${\mathrm{\ell }}_v$ in the unique sense of [F2], and $v\mathrm{\ne }u\otimes u$. Then by [F3] the self-corrected tensor test rejects with probability at least $1\mathrm{/}4-4{\epsilon }_0-2{\epsilon }_0=1\mathrm{/}4-3\mathrm{/}50=19\mathrm{/}100$, and the $(\mathrm{T})$ constraints are exactly the outcomes of that test, one for each choice of $(r,s,y,y^{\mathrm{\prime }},Y)$; hence at least $(19\mathrm{/}100)L$ of them are violated and the system violates at least $(19\mathrm{/}100)\mathrm{/}5>1\mathrm{/}500=\rho$ of its constraints.

Third and fourth soundness cases: suppose in addition $v=u\otimes u$. If the vector $u$ does not satisfy every equation of [F1], then the fraction of $z$ with $A(z)\odot v\mathrm{\ne }b(z)$ is exactly $1\mathrm{/}2$ by the random subsum clause, and for each such $z$ the fraction of auxiliary points $Y$ with $g(Y)+g(A(z)+Y)\mathrm{\ne }b(z)$ is at least $1-2{\epsilon }_0$ by [F4] applied to the two uniform points $Y$ and $A(z)+Y$; hence at least $\frac{1}{2}(1-2{\epsilon }_0)=\frac{49}{100}$ of the $(\mathrm{S})$ constraints are violated and the system violates at least $\frac{49}{500}>\rho$ of its constraints. If instead $u$ satisfies every equation, then by the exact extension equivalence of [F1] the input prefix $u_1\cdots u_n$ lies in $\mathrm{SAT}(C)$. For $n\ge 1$, writing $d:=\mathrm{\#}\{i:x_i\mathrm{\ne }{u}_i\}\mathrm{/}n$ gives $d\ge \delta (x,\mathrm{SAT}(C))$, and for each such $i$ the auxiliary point $y$ is uniform and independent of everything else, so by [F4] the fraction of $y$ with ${\mathrm{Corr}}_f(e_i;y)=u_i\mathrm{\ne }{x}_i$ is at least $1-2{\epsilon }_0$; hence at least $d(1-2{\epsilon }_0)\ge \frac{49}{100}\delta (x,\mathrm{SAT}(C))$ of the $(\mathrm{C})$ constraints are violated, whence the system violates at least $\frac{49}{500}\delta (x,\mathrm{SAT}(C))$. For $n=0$, an equation-satisfying $u$ means the empty input is accepted by [F1], so $\delta =0$ and the required bound is immediate; if the empty input is rejected then every $u$ fails an equation and the preceding subsum case applies.

Steps 3.1, 3.2, 3.3 and 3.4 cover every labeling: either a table is more than ${\epsilon }_0$ far from linear (step 3.2), or both are within ${\epsilon }_0$ of linear tables ${\mathrm{\ell }}_u,{\mathrm{\ell }}_v$ with $v\mathrm{\ne }u\otimes u$ (step 3.3), or $v=u\otimes u$ and $v$ fails an equation (step 3.4, first part), or $v=u\otimes u$ satisfies every equation and the comparison family charges the distance of $x$ from $\mathrm{SAT}(C)$ (step 3.4, second part). In each case ${\mathrm{UNSAT}}_{x\cup b}(P(C,X))\ge \rho \delta (x,\mathrm{SAT}(C))$ with $\rho =1\mathrm{/}500$, and step 3.1 gives perfect completeness, so by [F5] the constructed system is an assignment tester with alphabet $\{0,1\}$, arity bound $6$ and rejection ratio $\rho$; its size, explicitness and construction time are those of step 2.1.