Proof. The three coordinates of \(D(x,a)\) are \[x_2a_3+a_2x_3,\qquad x_1a_3+a_1x_3,\qquad x_1a_2+a_1x_2.\] When \(a=tv\), every term in \(v\cdot D(x,a)\) occurs twice, so their sum is zero. When both arguments are multiples of \(v\), each coordinate of the polar expression is zero. Thus \(Q|_A\) is binary additive, and the parametrization of \(U_A\) by \(A\oplus D_A\) is a binary linear bijection. Its dimension is \(d+2d=b\).

Every \(z\in A\) annihilates \(D_A\) under the trace pairing. The annihilator has binary dimension \(3d-2d=d\), so it is exactly \(A\). Finally, for each coordinate line \(A=Fe_i\), the space \(U_A\) contains \((Fe_i,0)\), because \(Q(te_i)=0\), as well as \(\{0\}\oplus D_A\). These three coordinate lines and their vertical hyperplanes span \(X\oplus B\). ◻

Proof. Choose independent uniform \(x_{ij}\in F\), for \(1\le i\le3\) and \(1\le j\le r\), and parametrize a binary linear map by \[z_i(t)=\sum_{j=1}^r x_{ij}t_j, \qquad t\in\mathbb F_2^r.\] Each nonzero input has uniform image in \(F^3\), so the probability that this map is not injective is at most \((2^r-1)q^{-3}\). Conditioned on injectivity, its image is a uniform binary \(r\)-subspace: every such subspace has the same number of ordered binary bases. Distinct nonzero binary inputs are linearly independent also over \(F\), so their images are independent uniform elements of \(F^3\). A union bound therefore shows that the nonproportionality condition fails with probability \(O_r(q^{-2})\), apart from the event of noninjectivity.

It remains to prove the alignment condition simultaneously for all \(g\). Fix a set \(E\) of more than \(3r\) distinct nonzero inputs in \(\mathbb F_2^r\). On an injective parametrization, the values of a binary linear \(g\) on a basis can be arbitrary vectors in \(F^3\). Thus alignment on all of \(E\) implies that the vector \[c=\bigl(\sqrt{z_1(t)z_2(t)z_3(t)}\bigr)_{t\in E}\] lies in the \(F\)-column span of the matrix with \(3r\) columns \[M_{t,(i,j)}=t_jz_i(t), \qquad t\in E,\quad 1\le i\le3,\quad 1\le j\le r.\] Conversely, membership supplies the basis values of such a \(g\). In particular, this column-membership condition already accounts for all possible maps \(g\).

First regard the \(x_{ij}\) as independent indeterminates and set \(L=\mathbb F_2(x_{ij})\). We claim that \(c\) is not in the column span of \(M\) even after extending scalars to an algebraic closure \(\overline L\). The following \(r^3\) elements are linearly independent over \(L\): \[\sqrt{x_{1j}x_{2k}x_{3l}}, \qquad 1\le j,k,l\le r.\] Indeed, after clearing denominators, a dependence would be a polynomial identity in the square roots of the indeterminates. The displayed monomials have distinct parity vectors, whereas coefficients polynomial in the \(x_{ij}\) have even exponents in those square roots. Terms from different parity vectors cannot cancel.

The expansion of \(c\) in these independent elements has coefficient vectors \[v_{jkl}=(t_jt_kt_l)_{t\in E}.\] Suppose that \(c\) belonged to the column span over \(\overline L\). Every row vector over \(L\) annihilating \(M\) would then annihilate \(c\). The independence just proved implies that it would annihilate every \(v_{jkl}\). By double annihilation in the finite-dimensional space \(L^E\), every \(v_{jkl}\) would belong to the column span over \(L\) itself.

For \(h\ge1\), let \(V_h\le L^E\) be the evaluation span of all positive-degree monomials in the binary coordinates \(t_1,\ldots,t_r\) of degree at most \(h\). Repeated indices in \(v_{jkl}\) give all monomials of degrees one and two as well as three, because \(t_i^2=t_i\) on the evaluation set. The preceding conclusion and the form of the columns therefore imply \[V_3\subseteq\operatorname{col}_L(M)\subseteq V_2\subseteq V_3.\] These three spaces are equal. Multiplication by any \(t_i\) sends \(V_2\) into \(V_3\), so preserves their common value. Since this space contains the degree-one monomials, it contains evaluations of every positive-degree monomial. These evaluations span all of \(L^E\): for any nonzero binary point, its usual indicator polynomial is a product of factors \(t_i\) and \(1+t_i\) with at least one factor \(t_i\), and thus has no constant monomial. Its restriction to \(E\) gives the corresponding point indicator. Consequently the column span would have dimension \(|E|>3r\), a contradiction.

To pass from this algebraic statement to finite fields, square the entries of both \(M\) and \(c\). The resulting matrices have polynomial entries, and the appended column has entries \(z_1(t)z_2(t)z_3(t)\). Let \(h=\mathop{\mathrm{rank}}_L M\le3r\). Squaring preserves rank over \(\overline L\), so the augmented squared matrix has a nonzero minor of size \(h+1\). This minor is a nonzero polynomial of degree at most \(2h+3\le6r+3\). All unaugmented minors of size \(h+1\) vanish identically, so the unaugmented rank cannot increase on specialization. It follows that specialized column membership forces this particular nonzero polynomial to vanish. For uniform independent \(x_{ij}\in F\), this event has probability at most \((6r+3)/q\) by the polynomial zero bound (Schwartz 1980, Corollary 1); see also the earlier sparse-polynomial formulation in (Zippel 1979, sec. 3.1).

If the alignment condition fails, it fails on some set \(E\) of size \(3r+1\). There are finitely many such sets depending only on \(r\); if \(2^r-1\le3r\) there are none and the condition is automatic. A union bound, followed by conditioning on injectivity, proves the lemma. ◻

Proof. The identity at height zero is immediate. Consider one higher level and condition on the selected child \((A,J)\). Write \(\Delta\) for its output difference. All child copies have the same function and the same inner noise law, so the law of \(\Delta\) is independent of the selected index.

We need also the conditional law of the child’s initial output. For any fixed child perturbation \(a\), Equation (12) gives \[C_{t-1}(u+a+h)+C_{t-1}(u+h) =C_{t-1}(u+a)+C_{t-1}(u) \qquad(h\in R_{t-1}).\] Thus the difference is invariant under these shifts, while the initial output is translated by every element of \(B\). On uniform input its initial output remains uniform conditional on the difference, even if the inner perturbation is also specified. All other initial child outputs remain independently uniform. Because the aggregate map is onto \(X\oplus B\), the initial aggregate \((x,y)\) is therefore uniform conditional on \((A,J,\Delta)\). In particular it is independent of the aggregate perturbation \(J\Delta\).

Conditional on \(\Delta\ne0\) and \(A\), the isomorphism \(J\) remains uniform, because the law of \(\Delta\) is independent of the selected child index. Thus \(J\Delta\) is uniform in \(U_A\setminus\{0\}\). The conditional uniformity just proved makes the initial aggregate independent of this update. Lemma 4 therefore gives parent change probability \(1-\theta\) conditional on a nonzero child difference. When \(\Delta=0\), the aggregate does not change. Consequently \(p_t=p_{t-1}(1-\theta)\), proving the identity. ◻

Proof. A shift supported on one child and lying in \(\ker\lambda_{t-1}\) is a parent shift with output translation zero. Each \(\psi_z\) vanishes on it, proving the first assertion.

Let \(T=\prod_{A,J}B\) be the space of child output translations, with aggregate map \(\mathcal A:T\to X\oplus B\). This map is onto. The sum of the child characters, minus \(z\) applied to the second component of \(\mathcal A\), vanishes whenever the first component of \(\mathcal A\) is zero: every such tuple of translations can be supplied by child shifts, giving a parent shift. The difference therefore factors uniquely through the first component of \(\mathcal A\), which is onto \(X\). Call this character \(\gamma_z\). Uniqueness shows that \(\gamma_z\) depends linearly on \(z\). Evaluating on a tuple supported at one child gives Equation (17). ◻

Proof. Restrict the full lift at the top to the fixed generic subspace of dimension \(r_0\). Follow the random leaf path, replacing the lift at each chosen child by the image lift just described. Let \(S_j\) be its domain after \(j\) steps, and let \(r_j=\dim S_j\), so initially \(r_j=r_0\) at \(j=0\). Continue with the zero space after extinction.

We spell out the conditioning that permits genericity to be used at every level. Let \(\mathcal F_j\) be the information in all path choices before the outgoing choice \((A_j,J_j)\) at step \(j\). The current space, lift, and map \(\gamma_j\) are \(\mathcal F_j\)-measurable. Conditional on \(\mathcal F_j\) and \(A_j\), the subspace \[E_{j,A_j} =\mathop{\mathrm{im}}\bigl[z\mapsto(\gamma_{j,z},z)|_{U_{A_j}}\bigr] \le U_{A_j}^*\] is fixed. The next domain and its rank are \[S_{j+1}=J_j^*E_{j,A_j}, \qquad r_{j+1}=\dim E_{j,A_j}.\] The rank is fixed before \(J_j\) is revealed. A uniform binary isomorphism \(J_j:B\to U_{A_j}\) makes \(S_{j+1}\) a uniformly random subspace of \(B^*\) of that rank. Therefore, if \(B_j\) is the indicator that \(r_j>0\) and \(S_j\) is nongeneric, then \[ \mathbb E[B_{j+1}\mid\mathcal F_j,A_j]\le\varepsilon_0. \tag{20}\] The next lift may depend on \(J_j\). This causes no restriction on the argument: genericity bounds every binary linear map \(g\) on the selected subspace, including the map supplied by that lift.

Let \(\Delta_j=H_{r_j}-H_{r_{j+1}}\ge0\). Conditional on \(\mathcal F_j\), the outgoing \(A_j\) is independent and uniform, and the rank-loss estimates above apply to the fixed current lift. Consequently \[ \mathbb E[\Delta_j\mid\mathcal F_j] \le3\theta+H_{r_0}2^{r_0}\theta B_j. \tag{21}\] For \(j=0\) the space is generic, so its expected drop is at most \(3\theta\). For \(j\ge1\), average Equation (21) over the preceding isomorphism using Equation (20). This gives the unconditional bound \[\mathbb E\Delta_j \le\bigl(3+H_{r_0}2^{r_0}\varepsilon_0\bigr)\theta \le4\theta.\] No independence between an incoming orientation and its subsequent lift has been assumed.

Summing the expected drops and using Equation (18), \[\mathbb E[H_{r_0}-H_{r_s}]\le4s\theta\le\frac{H_{r_0}}2.\] Extinction requires a total drop of \(H_{r_0}\), so \(\Pr[r_s=0]\le1/2\). At a leaf, \(P_0=R_0=B\) and its lift consists of the characters themselves. Conditional on any surviving rank \(r_s>0\), an independent uniform symbol in \(B\) is detected with probability \(1-2^{-r_s}\ge1/2\). Every surviving functional is a restriction of the original family along the selected leaf, so such a detection implies a detection by that family of the embedded noise \(\xi_s\). Multiplying the two bounds proves Equation (19). ◻

Proof of Lemma 2. Choose \(r_0\) sufficiently large that \[\exp(1-H_{r_0}/8)\le p_*.\] Then choose \(\varepsilon_0\) as in Equation (11) and fix \(d\), and hence \(b=3d\) and \(\theta\), using Lemma 7. Construct the height \(s\) in Equation (18) and the quotient \((V_0,B,\overline C,\nu)\) above. Lemma 8 gives \[ p_s\le(1-\theta)^s \le\exp(-\theta s) \le\exp(\theta-H_{r_0}/8) \le p_*. \tag{23}\] Set \(r_*=b+2\). All choices so far depend only on \(p_*\).

We now enlarge the output space. The point of using random injections \(B\to K\) is that a family of restriction rank at least \(b+2\) on \(K\) restricts onto all of \(B^*\) along most injections. A copy of the base gadget for each injection will therefore turn its full-restriction detection bound into the required high-rank bound.

Fix \(\ell\ge b+2\) and write \(K=\mathbb F_2^\ell\). Let \(\mathcal L\) be the finite set of all binary linear injections \(L:B\to K\). Take a product \(P=\prod_{L\in\mathcal L}V_0\) and define \[\widetilde C((x_L)_L)=\sum_{L\in\mathcal L}L\overline C(x_L).\] The product of shift subspaces \(T=\prod_L B\le P\) acts on this output through the linear map \[\Lambda:T\longrightarrow K, \qquad \Lambda((b_L)_L)=\sum_L Lb_L.\] This map is onto, because every nonzero vector of \(K\) is in the image of some injection \(B\to K\). Quotient by its kernel inside \(T\): \[\mathcal V=P/\ker\Lambda.\] The map \(\widetilde C\) descends to \(C:\mathcal V\to K\), and \(T/\ker\Lambda\) identifies with the required shift subspace \(K\). This proves Equation (1).

On \(P\), choose a uniform \(L\in\mathcal L\) and update only that copy by an independent sample from \(\nu\). Let \(\mu\) be the resulting law after the quotient. On uniform product input the output sum changes exactly when the selected copy’s output changes, because \(L\) is injective. Uniform input pushes to uniform input on the quotient, so the change probability is still \(p_s\). Equation (23) proves Equation (2). Every noise distribution used here is obtained from uniform finite choices by pushforward, and therefore is rational.

It remains to establish detection for an arbitrary \(G\le\mathcal V^*\). Let \(S=G|_K\le K^*\), of dimension \(r\ge r_*\). Pull \(G\) back to \(P\) and then restrict to its copy of \(V_0\) indexed by \(L\); denote the resulting subspace of \(V_0^*\) by \(G_L\). Its restriction to that copy’s shift subspace \(B\) is exactly \[G_L|_B=L^*S.\] To see this, a shift \(b'\in B\) supported on copy \(L\) represents the shift \(Lb'\in K\) in the quotient, so a character restricting to \(z\in S\) evaluates there as \(z(Lb')\).

The map \(L^*:S\to B^*\) fails to be onto if and only if there is a nonzero \(b'\in B\) with \(Lb'\in S^\perp\). For each such fixed \(b'\), a uniform injection \(L\) makes \(Lb'\) uniform among the nonzero vectors of \(K\). Hence \[\Pr_L[Lb'\in S^\perp] =\frac{2^{\ell-r}-1}{2^\ell-1} \le2^{-r}.\] A union bound gives \[\Pr_L[L^*S\ne B^*] \le(2^b-1)2^{-r} \le2^{b-r}\le\frac14.\] On each of the remaining copies, Equation (22) gives detection probability at least \(1/4\) by \(G_L\), and thus by \(G\) on the embedded noise. Averaging over the selected copy yields detection probability at least \(\frac34\cdot\frac14=\frac{3}{16}\ge\frac18\), proving Equation (3). The construction works for every \(\ell\ge b+2\), with the already fixed \(r_*=b+2\), as required.

For completeness, all choices are effective when \(p_*\) is rational. Choose an integer \(m\ge0\) with \(2^{-m}\le p_*\) and then choose \(r_0\) with \(H_{r_0}\ge8(m+1)\); since \(e^{-m}\le2^{-m}\), this ensures the initial bound on \(r_0\). Choose rational \(\varepsilon_0\) satisfying Equation (11). For successive integers \(d\) with \(3d\ge r_0\), enumerate the binary subspaces of \(\mathbb F_{2^d}^3\) and the linear maps in the definition of genericity. This tests genericity exactly and computes the fraction of nongeneric spaces at each rank \(1,\ldots,r_0\). Lemma 7 ensures that eventually all these fractions are at most \(\varepsilon_0\). Fix the first such field and a generic rank-\(r_0\) space. The remaining products, isomorphisms, injections, quotients, function tables, and rational noise laws are obtained by finite enumeration and binary linear algebra. This gives the asserted terminating construction. ◻

Proof. Replace each variable \(v\) by one hundred clones \((v,c)\), \(c\in[100]\). For each original occurrence, choose its three clones uniformly subject to choosing distinct clones whenever positions have the same underlying variable. List all the resulting occurrences and give them the corresponding conditional weights. There are at most \(100^3\) choices per original occurrence. Giving all clones their original variable’s label proves the completeness assertion.

For the upper bound fix arbitrary clone labels, and let \[t_v=\frac1{100}\sum_{c=1}^{100}(-1)^{x_{(v,c)}}.\] First choose clones independently, without conditioning on distinctness. The satisfaction probability of occurrence \(e\) is \[\frac{1+(-1)^{b_e}t_{v_{e,1}}t_{v_{e,2}}t_{v_{e,3}}}{2}.\] Round each bias to a majority label, resolving zero biases arbitrarily. For every equation violated by this rounded assignment, the signed product in the numerator is nonpositive, so its satisfaction probability is at most \(1/2\). The other equations have probability at most one. The weighted mean is therefore at most \((1+\mathop{\mathrm{OPT}}(\mathcal E))/2\). The probability of a forbidden collision among the independently chosen clones is at most \(3/100\), by a union bound over the three pairs of positions. Conditioning on its complement changes the expectation of any \([0,1]\)-valued function by at most \(3/100\). This proves the bound. All conditional probabilities have constant-size denominators apart from their original occurrence weights. ◻

Proof. Fix the near-satisfying global bit assignment. Give every reduced support a valid answer as follows. At a singleton use its global bit. At a retained equation use its first two global bits and set the third to the unique value satisfying the equation. These choices depend only on the support, including its occurrence IDs, and therefore define an answer for every exact key independently of its origin.

At an orbit representative, evaluate its reduced table on this answer and apply \(C\). This defines a vertex labeling. The equivariance of \(C\) under \(K\) implies that its restored answer is evaluation of the actual reduced table followed by \(C\), in agreement with Equation (27).

With probability at least \(1-k\xi\), every equation in \(U\) is satisfied by the global assignment. On such a tuple, the support answers used for every table are projections of the same full answer \(z_U\in L_U\), whose first coordinate is one. Consequently the two sides of Equation (29) are \[C(Pz_U)\quad\text{and}\quad C(Pz_U+a(l^\top z_U)).\] Since \(z_U\ne0\), the vector \(Pz_U\) is uniform in \(\mathcal V\), independently of \(a,l\), and \(l^\top z_U\) is an independent fair bit. The test therefore fails with probability at most \(p_*/2\) on these tuples. Adding the probability of a tuple containing an unsatisfied equation proves the bound. ◻

Proof. We derive this consequence from the Grassmann expansion theorem of Khot–Minzer–Safra (Khot et al. 2023, Theorem 1.12 in the 2018 revision), using the matrix chart of Barak–Kothari–Steurer (Barak et al. 2019, Definition 3.2 and Lemmas 3.3–3.7).

The Grassmann graph on an ambient binary space \(E\) has the \(\ell\)-dimensional subspaces as vertices; two vertices are adjacent when their intersection has dimension \(\ell-1\). The retention of a nonempty vertex set is the probability that a uniform vertex in the set has a uniform neighbor still in the set. The cited theorem says that a set of retention at least a fixed \(\zeta>0\) has positive relative density in some interval \[\{L:A_0\subseteq L\subseteq B_0\}, \qquad \dim A_0+\operatorname{codim}_E B_0\le r.\] The density bound and \(r\) depend only on \(\zeta\). The theorem holds for all sufficiently large \(\ell\), and then all sufficiently large \(\dim E\).

Equality acceptance is the average of the retention probabilities of the nonempty fibers \(f^{-1}(y)\) under the matrix step, weighted by their uniform masses. Some fiber \(S\) therefore has retention at least \(\eta\). The probability that either perturbation factor is zero is \[p_0=2^{-\ell}+2^{-m}-2^{-\ell-m}.\] Choose the dimension thresholds so that \(p_0\le\eta/2\). Conditional on both factors being nonzero, the retention of \(S\) is at least \((\eta-p_0)/(1-p_0)\ge\eta/2\).

For each matrix put \[L_M=\{(x,M^\top x):x\in\mathbb F_2^\ell\} \subseteq E:=\mathbb F_2^\ell\oplus\mathbb F_2^m.\] The map \(M\mapsto L_M\) is a bijection onto the chart \(\mathcal C\) of subspaces whose projection onto the first summand is invertible. Since \[\dim(L_M\cap L_N)=\ell-\mathop{\mathrm{rank}}(M-N),\] the neighbors within the chart correspond exactly to nonzero rank-one matrix differences. Each chart vertex has \((2^\ell-1)(2^m-1)\) such neighbors, whereas its full Grassmann degree is \((2^\ell-1)(2^{m+1}-2)\): choose a hyperplane in the vertex and then a one-dimensional extension in the quotient by that hyperplane, other than the vertex itself. Thus exactly half of its neighbors lie in the chart. Over \(\mathbb F_2\), every nonzero rank-one matrix has a unique factorization \(a l^\top\) with nonzero factors. The lifted set \(\widetilde S=\{L_M:M\in S\}\) consequently has Grassmann retention at least \(\eta/4\).

Apply the expansion theorem with \(\zeta=\eta/4\), obtaining density \(\alpha\) on an interval with \(\dim A_0+\operatorname{codim}_E B_0\le r_{\rm s}\). Intersecting this interval with \(\mathcal C\) only increases the relative density of \(\widetilde S\), since \(\widetilde S\subseteq\mathcal C\), and the intersection is nonempty. A basis \((d_i,s_i)\) of \(A_0\) specifies \(A_0\subseteq L_M\) by the equations \(d_i^\top M=s_i^\top\). For the standard dot product on \(E\), a basis \((t_j,q_j)\) of \(B_0^\perp\) specifies \(L_M\subseteq B_0\) by \(Mq_j=t_j\). Their simultaneous solution set is a slice of the required form, with at most \(r_{\rm s}\) equations of either kind. On at least an \(\alpha\) fraction of this slice, \(f\) equals the value defining \(S\). This proves the conclusion with \(z=0\) and \(u\) equal to that value.

The constants \(\alpha,r_{\rm s}\) were chosen using only \(\eta\). Since \(\dim E=\ell+m\), after fixing \(\ell\) the remaining dimension threshold is absorbed into \(m_0(\eta,\ell)\). No folding condition was used. The fiber argument is the equality consequence in (Barak et al. 2019, Lemma 2.3); numbered references to that paper use its arXiv version 1. ◻

Proof. For \(\sigma\in K^*\) define the sign function \(f_{U,\sigma}(P)=(-1)^{\sigma(F_U(P))}\). A frequency on the matrix domain is a tuple \(g=(g_i)_{i=0}^{m-1}\) of functionals in \(\mathcal V^*\); its character at \(P\) is \((-1)^{\sum_i g_i(Pe_i)}\). All Fourier coefficients use uniform probability measure. Translation by \(a l^\top\) multiplies this character by \((-1)^{\sum_i l_i g_i(a)}\). Averaging over uniform \(l\) therefore gives the eigenvalue \[\Lambda_g=\Pr_{a\sim\mu}[g_i(a)=0\text{ for every }i].\] It lies in \([0,1]\). By Lemma 2, it is at most \(7/8\) whenever \[\dim\mathop{\mathrm{span}}\{g_i|_K:0\le i<m\}\ge r_*.\] Indeed the span of the \(g_i\) is a subspace of \(\mathcal V^*\) to which the lemma applies.

Expanding equality by a uniform output character, and then using Fourier orthogonality, expresses the test acceptance as \[\mathbb E_{U,\sigma}\sum_g \lvert \widehat f_{U,\sigma}(g)\rvert^2\Lambda_g.\] Parseval gives total squared mass one for each sign function. If \(B\) is the average squared mass on restricted ranks at least \(r_*\), then \(0.99\le1-B/8\), so \(B\le0.08\). In particular, at least \(0.9\) of the average mass lies on ranks below \(r_*\).

When \(a\) is instead uniform in \(K\), the eigenvalue at \(g\) is \(2^{-\dim\mathop{\mathrm{span}}\{g_i|_K\}}\). The preceding mass thus gives the lower bound in Equation (36). This perturbation leaves \(T\) fixed, so the expression there is precisely the average of the ordinary shortcode equality tests at fixed \((U,T)\). Its lower bound is \(14.4\eta\). If \(q\) is the probability that the inner acceptance is at least \(4\eta\), then the average is at most \(4\eta+q\). Thus \(q\ge10.4\eta\ge10\eta\). ◻

Proof. Fix \((U,T)\) for which the surrogate acceptance is at least \(4\eta\), and write \(f(M)=F_U(M,T)\). Let \(B\) be the union, in the matrix domain, of all good row fibers, over every possible \(A,S_0\). Suppose that its uniform measure is less than \(\eta\). Change \(f\) at the entries of \(B\), replacing each by an independent uniform element of \(K\). Each matrix receives one replacement, even when several good row fibers overlap there. Both endpoints of the shortcode step are uniform matrices. Consequently every such modification changes acceptance by at most \(2\Pr[B]\), and the modified function has acceptance at least \(2\eta\).

We show that the random replacements can be chosen so that they contribute less than \(\alpha/4\) of the size of every simultaneous row and column slice as matches with every target \(Mz+u\). Put \(r=r_{\rm s}\). A nonempty slice with at most \(r\) row and \(r\) column specifications has homogeneous space \[\mathop{\mathrm{Hom}}\bigl(\mathbb F_2^m/\mathop{\mathrm{span}}\{q_j\},\ \bigcap_i\ker d_i^\top\bigr).\] Its size \(n_{\mathcal S}\) is therefore at least \(2^{(\ell-r)(m-r)}\). Padding the lists of specifications with zero equations, the number of slice–target descriptions is at most \(2^{(2r+1)(\ell+m)}\).

For a fixed description, count only matches at randomized entries and assign a deterministic zero contribution to the other entries. These are independent variables in \([0,1]\), with total mean at most \(2^{-\ell}n_{\mathcal S}<\alpha n_{\mathcal S}/8\). Hoeffding’s inequality (Hoeffding 1963, Theorem 2, equation (2.6)) bounds the probability of at least \(\alpha n_{\mathcal S}/4\) such matches by \(\exp(-\alpha^2 n_{\mathcal S}/32)\). The union bound over all descriptions is thus at most \[\exp\left((2r+1)(\ell+m)\log2 -\frac{\alpha^2}{32}2^{(\ell-r)(m-r)}\right),\] which tends to zero as \(m=1+2k\) grows. Fix replacements with the asserted property.

Consider any slice of the allowed type. If its row fiber was good, every entry of that fiber belongs to \(B\), and its modified agreement is less than \(\alpha/4\). If the row fiber was not good, the original agreement with each target on the slice was less than \(\alpha/2\). The unmodified matches form a subset of those original matches, and the randomized matches add less than \(\alpha/4\). The modified agreement is then less than \(3\alpha/4\). Padding shorter row systems by zeros shows that these two cases cover every slice in Theorem 14. That theorem now contradicts the modified function’s acceptance at least \(2\eta\). Its applicability does not require the modification to preserve folding.

It follows that \(\Pr[B]\ge\eta\). For each \(M\in B\), at least one matrix \(A\) has a good row fiber containing \(M\). The uniform choice of \(A\) hits that particular matrix with probability \(2^{-\ell r_{\rm s}}\). Hence, at this fixed \((U,T)\), the probability of good data is at least \(\eta2^{-\ell r_{\rm s}}\). Lemma 17 supplies at least \(10\eta\) of such pairs \((U,T)\), proving Equation (37). All counting and concentration bounds depended only on the fixed parameters and \(m\), as required.

The remaining assertion does not use high test acceptance or largeness of \(k\). Fix any positive integer \(k\), a family satisfying Equation (35), and any good row advice. Fix a witness, write its column specifications as \(Mq_j=t_j\), and put \(Z=\mathop{\mathrm{span}}\{q_j\}\). Nonemptiness of the slice makes the prescribed values consistent: they determine a linear map \(t:Z\to K\) with \(t(w)=Mw\) throughout the slice. Replacing \(z\) by \(z+w\) and \(u\) by \(u+t(w)\) for \(w\in Z\) therefore preserves the target. It suffices to show that the coset \(z+Z\) contains a vector of first bit one.

Otherwise \(z\) and every vector in \(Z\) have first bit zero. Put \(H=\ker A\). For each \(h\in H\), translation \(M\mapsto M+h e_0^\top\) preserves the row fiber, the column specifications, and the target. By folding it translates \(F_U(M,T)\) by \(h\). The action is free, and in each of its \(H\)-orbits at most one matrix can satisfy the target equality. The agreement is at most \[|H|^{-1}=2^{-\ell+\mathop{\mathrm{rank}}A} \le2^{-(\ell-r_{\rm s})}<\alpha/8,\] contradicting goodness. Choose \(w\in Z\) for which \(z+w\) has first bit one and make the corresponding changes to \(z\) and \(u\). They preserve the original agreement fraction. Choose a witness and such a representative using a fixed order on the finite possibilities. This choice uses only the row advice and the fixed table family. Its vector \(z\) lies in \(\mathcal A\), so the set is nonempty; since \(\dim Z\le r_{\rm s}\), its size is at most \(2^{r_{\rm s}}\). ◻

Proof. Combine the two components into a \(\mathcal V\)-valued table and put \(n=|\mathcal V|\). On an unprojected equation block the two slopes are independent uniform elements of \(\mathcal V\). On a singleton block the padded pair of slopes is an equal mixture of \[(a,0),\qquad (0,a),\qquad (a,a), \qquad a\text{ uniform in }\mathcal V.\] Call these pair laws \(P_0\) and \(Q_0\), respectively. The likelihood ratio \(dQ_0/dP_0\) is \(n\) at \((0,0)\), \(n/3\) at the other \(3(n-1)\) points on the three displayed lines, and zero elsewhere. Thus \[\chi^2(Q_0\Vert P_0) :=\mathbb E_{P_0}\left[\left(\frac{dQ_0}{dP_0}-1\right)^2\right] =\frac{n-1}{3}.\] The one-block mixture \((1-\beta)P_0+\beta Q_0\) consequently has chi-squared divergence \(\beta^2(n-1)/3\) from \(P_0\). Blocks are sampled independently, including when their question IDs coincide. Multiplying their likelihood ratios gives divergence \[ \left(1+\frac{n-1}{3}\beta^2\right)^k-1=o(1), \tag{39}\] because \(n\) is fixed and \(k\beta^2=k^{-1/3}\) tends to zero. Total variation is at most one half the square root of this expression.

For a projection onto the third bit of equation \(e\), the padded intercept acquires the term \(b_e a\), where \(a\) is that singleton’s slope. The original intercept is independent and uniform in \(\mathcal V\). Adding the sum of these terms leaves it uniform and independent even after all projection choices and slopes are given. The preceding slope estimate therefore proves the assertion for the entire table. Neither the slope laws nor the bound in Equation (39) depend on the equation IDs or their right-hand sides. ◻

Proof. First use unrestricted sampling of \(U,A,M,T\), setting \(S_0=AM\). Let \(\mathcal J\) be the event that \((U,T,A,S_0)\) is good and \(M\) satisfies its chosen column specifications. Let \(\mathcal M\) be equality with the chosen target, declaring this event false off good data. Within a good row fiber the nonempty column slice imposes at most \(\ell r_{\rm s}\) additional scalar linear equations. Hence Lemma 18 gives \[\Pr[\mathcal J]\ge g_0\,2^{-\ell r_{\rm s}}, \qquad \Pr[\mathcal J\cap\mathcal M]\ge(\alpha/2)\Pr[\mathcal J].\] It follows that \[ \Pr[\mathcal J\cap\mathcal M] -(\alpha/4)\Pr[\mathcal J] \ge\frac{\alpha g_0}{4}\,2^{-\ell r_{\rm s}}. \tag{43}\]

Both events in this expression depend only on \((U,A,M,T)\). Adding the independent \(A\) to Lemma 19 preserves its variation bound. We may therefore compare the two event probabilities with their values in the padded experiment. If the total variation distance is \(v_k=o(1)\), the difference in Equation (43) changes by at most \((1+\alpha/4)v_k\). For all sufficiently large \(k\) the padded difference is at least \(\gamma_1\).

Now condition on \(D\). The remaining \(M_O\) is uniform on the row fiber \(AM_O=S_O\). The padded \(U\)-advice, and therefore its chosen witness and answer set, are fixed. On good data let \(p_D\) be the conditional probability of the projected column slice, and, when \(p_D>0\), let \(q_D\) be its conditional equality fraction. Put \(p_D=0\) on data that are not good, and put \(q_D=0\) when \(p_D=0\). Sharing gives \(F_U(M_O\bar\pi,T_O\bar\pi)=F_O(M_O,T_O)\), so the padded difference is exactly \[\mathbb E_D\bigl[p_D(q_D-\alpha/4)\bigr]\ge\gamma_1.\] The integrand is nonpositive outside the event consisting of goodness, \(p_D>0\), and \(q_D\ge\alpha/4\), and it is at most one everywhere. That event thus has probability at least \(\gamma_1\) and has precisely the asserted properties. The law comparison applied to events depending only on \((U,A,M,T)\); conditioning on \(D\) here only identifies where their positive difference occurs in the projected experiment. ◻

Proof. Put \(Z'=\bar\pi Z\), so \(\dim Z'\le r_{\rm s}\). The projected column specifications in the row fiber fix the restriction \(N|_{Z'}\) to a linear map \(b:Z'\to H\). The resulting affine slice is nonempty; choose one \(N_*\) in it. For every \(\sigma\in K^*\) define \[C_\sigma=\mathbb E\bigl[f_\sigma(N)(-1)^{\sigma(Nz')} \mid N|_{Z'}=b\bigr].\] The character expansion of Equation (42) gives \[\mathbb E_\sigma\bigl[(-1)^{\sigma(M_0z'+u)}C_\sigma\bigr] \ge\alpha/4, \qquad\text{so}\qquad \mathbb E_\sigma|C_\sigma|\ge\alpha/4.\] Exactly a fraction \(2^{-\dim H}\) of the characters have trivial restriction to \(H\). Since \(\dim H\ge\ell-r_{\rm s}\) and \(|C_\sigma|\le1\), Equation (33) implies \[ \mathbb E_\sigma\bigl[\mathbf 1_{\{\sigma|_H\ne0\}}|C_\sigma|\bigr] \ge\alpha/8. \tag{45}\]

The annihilator in \(X^*\) of matrices vanishing on \(Z'\) is \(H^*\otimes Z'\). For \(\theta_\sigma=(\sigma|_H)\otimes z'\), Fourier expansion on the affine slice therefore gives \[C_\sigma =\sum_{\Phi\in\theta_\sigma+H^*\otimes Z'} \widehat f_\sigma(\Phi) (-1)^{\langle\Phi+\theta_\sigma,N_*\rangle}.\] This sum has \(2^{\dim H\dim Z'}\le2^{\ell r_{\rm s}}\) terms. Cauchy–Schwarz, first on each sum and then in the average over \(\sigma\), shows from Equation (45) that \[\begin{align*} &\mathbb E_\sigma\left[ \mathbf 1_{\{\sigma|_H\ne0\}} \sum_{\Phi\in\theta_\sigma+H^*\otimes Z'} |\widehat f_\sigma(\Phi)|^2\right]\\ &\hspace{15mm}\ge 2^{-\ell r_{\rm s}} \mathbb E_\sigma\bigl[\mathbf 1_{\{\sigma|_H\ne0\}}C_\sigma^2\bigr] \ge 2^{-\ell r_{\rm s}}(\alpha/8)^2. \end{align*}\] This is a lower bound on the probability that the \(O\)-decoder samples a nontrivial restriction and a frequency in the indicated coset.

Every such frequency has the form \(\Phi=(\sigma|_H)\otimes z'+\Psi\) with \(\Psi\in H^*\otimes Z'\). For the decoder’s choice of \(h\) it satisfies \[\Phi(h)=z'+\Psi(h)\in z'+Z'.\] As already proved, a frequency of positive mass gives first bit one. Equation (40) therefore places the returned vector in \(\bar\pi\mathcal A\). Independently, the \(U\)-decoder samples uniformly from \(\mathcal A\) and chooses a preimage with probability at least \(1/|\mathcal A|\ge2^{-r_{\rm s}}\). Multiplying the bounds proves Equation (44). ◻

Proof of Proposition 16. Use the two decoders above. Lemma 20 supplies a set of joint data of probability at least \(\gamma_1\), and Lemma 21 gives the stated conditional agreement on that set. Thus one may take \[\gamma=\gamma_1\,2^{-\ell r_{\rm s}}(\alpha/8)^2\,2^{-r_{\rm s}}>0.\] The largeness requirements for \(k\) come only from Theorem 14, the concentration bound in Lemma 18, and the total variation estimate in Lemma 19. They are uniform in the parity instance and table family. Witness choices and Fourier sampling need not be efficient: they define strategies in a finite game for the soundness argument. Finally, averaging over the provers’ independent random tapes also gives deterministic strategies with at least the same agreement probability. ◻

Proof. Fix an arbitrary pair of local randomized strategies in the advice experiment. We first condition on \(A\) and combine the two visible advice maps into \[D_O=(T_O,S_O):L_O\longrightarrow E_A, \qquad E_A=W\oplus\mathop{\mathrm{im}}A.\] Conditional on the questions and projection choices, the intercept \(c_O\) and all block slope columns of \(D_O\) are independent uniform elements of \(E_A\). Indeed, the columns of \(T_O\) and \(M_O\) are independent and uniform, and applying \(A\) to a uniform column gives a uniform element of \(\mathop{\mathrm{im}}A\). This coefficient law depends only on whether a block is an equation or a singleton, and not on any equation ID, variable ID, or selected position. In particular, \(c_O\) is independent of all block data.

Call coordinate \(i\) clean if it is projected to a singleton and its one advice slope \(d_i\in E_A\) is zero. Conditional on \(A\), the clean indicators are independent, with common probability \[ p_A=\frac{\beta}{\lvert E_A\rvert} =\beta\,2^{-\dim W-\mathop{\mathrm{rank}}A}. \tag{49}\] More precisely, for every equation occurrence \(e\) and position \(j\in[3]\), \[ \Pr[e_i=e,\ i\text{ is a clean singleton at position }j\mid A] =\omega_e\,\frac{\beta}{3\lvert E_A\rvert}. \tag{50}\] Thus, conditional on being clean, a coordinate has precisely the ordinary equation–variable distribution.

Let \(I\subseteq[k]\) be the clean set. For the analysis, let \(R\) consist of \(A\), \(I\), the original intercept \(c_O\), and the following data for every \(i\notin I\): its equation occurrence, whether the block was retained or projected, the selected position in the latter case, and its advice slope columns. No witness, decoder output, agreement event, or response randomness is included in \(R\).

For each value \(R=r\) of positive probability, regard the clean set \(I\) recorded in \(r\) as fixed. When \(I\) is nonempty, we will use \(r\) as constant data when defining two strategies for \(G_{\mathcal E}^{\otimes\lvert I\rvert}\). Each strategy will reconstruct one original advice input from its own product-game questions, apply the corresponding original response rule, and retain the answers in the clean slots.

Conditional on \(R=r\), the pairs \[(e_i,v_{e_i,j_i}),\qquad i\in I,\] are independent question pairs of \(G_{\mathcal E}\). Indeed, conditional on \(A\), the coordinate data are independent, and Equation (50) shows that conditioning on the clean mask preserves the ordinary law in each clean coordinate. The outside coordinate data and the independent intercept impose no further condition on these pairs.

We now verify the two reconstructions, including the affine intercept shared across the blocks. An equation with right-hand side \(b_e\) has actual bits \(x,y,b_e t_0+x+y\). Pulling back a singleton slope \(d_i\) thus produces the two slopes \[ (d_i,0),\quad (0,d_i),\quad (d_i,d_i) \tag{51}\] at positions one, two, and three, respectively. The intercept of \(D_U=D_O\bar\pi\) is \[ c_U=c_O+ \sum_{\substack{i\text{ projected to a singleton}\\j_i=3}} b_{e_i}d_i. \tag{52}\] For a clean coordinate, every slope in Equation (51) is zero and its contribution to Equation (52) is zero. All remaining terms in that equation are determined by \(r\).

The equation side receives its occurrences \(e_i\) for \(i\in I\). Together with \(r\), they specify all of \(U\). Its two advice slopes in each clean block are zero, while \(r\) determines every other slope and the full intercept. These coefficients reconstruct both padded advice maps without using any clean selected position or variable question. The variable side receives the variable question for each \(i\in I\). Together with \(r\), these specify all of \(O\). Its clean singleton slopes are zero, and \(r\) supplies every other slope and the original intercept. These coefficients reconstruct its two advice maps without using any clean equation. Repeated IDs across different blocks cause no additional restriction: questions were sampled independently with replacement, and answers use the local copies specified in Section 4.

These reconstructions define the promised product-game strategies: each side applies its original response rule to the reconstructed input and retains its answers in the slots \(I\), in their original order. Their equation answers are satisfying triples because the original answers are valid. For every realization of the clean questions and response randomness, full agreement in the advice experiment implies acceptance in every clean slot. If \(I=\varnothing\), the conditional success probability is at most one. Otherwise, \[\Pr[\bar\pi a_U=a_O\mid R=r] \le \mathop{\mathrm{val}}(G_{\mathcal E}^{\otimes\lvert I\rvert}) \le \left(1-\frac{1}{3600}\right)^{\lvert I\rvert}.\] The first inequality uses the strategies just constructed and the conditional product law. The second uses Theorem 22 and Equation (24). The original response rules are evaluated only at their original local inputs; \(r\) indexes the auxiliary product-game strategies. Thus the final bound holds for every \(r\), including \(I=\varnothing\) when its right-hand side is interpreted as one.

Finally, conditional on \(A\), the size of \(I\) has distribution \(\operatorname{Binomial}(k,p_A)\). Averaging the preceding inequality first over \(R\) conditional on \(A\), and then over \(A\), gives \[\begin{align*} \Pr\bigl[\bar\pi(a_U)=a_O\bigr] &\le \mathbb E_A\left(1-\frac{p_A}{3600}\right)^k\\ &\le\left(1-\frac{\beta\,2^{-\dim W-r_{\rm s}}}{3600}\right)^k\\ &\le \exp\!\left( -\frac{k\beta\,2^{-\dim W-r_{\rm s}}}{3600} \right), \end{align*}\] since \(\mathop{\mathrm{rank}}A\le r_{\rm s}\). Substituting \(k\beta=k^{1/3}\) proves Equation (48). ◻

Proof. Completeness is Lemma 13. For soundness, fix a labeling of \(\mathcal G\). Its restored table functions satisfy the folding and sharing identities of Section 4. Proposition 16 supplies a constant \(\gamma>0\) and, for every sufficiently large cube \(k\), gives local advice strategies with agreement at least \(\gamma\) whenever those functions have matrix-test acceptance at least \(0.99\). For all sufficiently large cubes \(k\), the upper bound in Equation (48) is smaller than \(\gamma\). Lemma 23 contradicts the existence of those strategies whenever \(\mathop{\mathrm{OPT}}(\mathcal E)\le4/5\). All thresholds are uniform over the parity instance. ◻

Proof. Write the occurrence weights as \(w_1,\ldots,w_h\). Start with \(n_e=\lfloor Qw_e\rfloor\), and add one to the \(Q-\sum_e\lfloor Qw_e\rfloor\) entries having largest fractional parts, breaking ties in a fixed order. Then \[n_e\ge0,\qquad \sum_e n_e=Q,\qquad |w_e-n_e/Q|\le1/Q.\] The weight differences sum to zero. Consequently, for every labeling, the change in the weight of its satisfied-occurrence set is at most \[\frac12\sum_{e=1}^h|w_e-n_e/Q| \le\frac{h}{2Q}\le\tau.\] Replace each occurrence \(e\) by \(n_e\) copies, omitting it if \(n_e=0\). The resulting unweighted multigraph \(H'\) has \(Q\) occurrences and \(|\mathop{\mathrm{val}}(H')-\mathop{\mathrm{val}}(H)|\le\tau\).

Orient each occurrence \(e\) of \(H'\) from \(u\) to \(v\), writing its constraint as \(a_v=\rho_e(a_u)\). Replace it by the path \[u\;--\;p_e\;--\;q_e\;--\;r_e\;--\;v,\] using three fresh interior vertices for every occurrence. Place all original vertices and all \(q_e\) on the left, and all \(p_e,r_e\) on the right. In the direction from \(u\) to \(v\), put identity permutations on the first three edges and \(\rho_e\) on the last. When expressing an edge in left-to-right orientation, invert its permutation if needed. Give all \(4Q\) edges equal weight.

Fix labels at the original vertices. A satisfied occurrence extends to four satisfied edges. A violated occurrence cannot extend to four, but propagating labels along the first three edges satisfies exactly three. Since the interiors are disjoint, these extensions can be chosen independently. Maximizing over the original labels gives the exact identity \[ \mathop{\mathrm{val}}(B)=1-\frac{1-\mathop{\mathrm{val}}(H')}{4}. \tag{54}\] This proves Equation (53).

A loop becomes a four-cycle with three distinct new vertices. Parallel occurrences have disjoint interiors. Thus each left–right vertex pair carries at most one edge, so \(B\) is simple. An inverse binary translation is the same translation, and an identity is translation by zero; the claimed constraint form is preserved.

Finally, \(Q\le h/\tau+1\) is polynomially bounded for fixed \(\tau\). Integer division and exact comparison of rational remainders compute the \(n_e\) in polynomial time and bit complexity. Listing their \(Q\) copies and the \(3Q\) new vertices is therefore polynomial as well. ◻

Proof of Theorem 1. Fix \(\varepsilon,\delta\in(0,1/2)\). Choose positive rational \(\varepsilon_0\le\varepsilon\) and \(\delta_0\le\delta\). We will take \(\tau\le1/200\) when applying the rounding and subdivision lemma. For any matrix game \(H\) satisfying the NO bound \(\mathop{\mathrm{val}}(H)\le99/100\), the resulting game \(B\) then satisfies \[ \mathop{\mathrm{val}}(B)\le1-\frac{1/100-\tau}{4}\le1-\frac1{800}. \tag{55}\] This gap does not depend on the alphabet. We can therefore use alphabet-independent repetition to choose its exponent before the latent construction fixes that alphabet. Choose an integer \(t\ge1\) such that \[ \left(1-\frac1{10240000}\right)^t\le\delta_0. \tag{56}\] For example, \(t\ge\lceil10240000\log(1/\delta_0)\rceil\) suffices. By Theorem 22, this exponent reduces every projection game of value at most \(1-1/800\) to value at most \(\delta_0\).

Choose positive rational parameters \[ p_*\le\frac{\varepsilon_0}{t},\qquad \tau\le\min\left\{\frac1{200},\frac{\varepsilon_0}{t}\right\}. \tag{57}\] Choose the latent rank threshold \(r_*\) from Lemma 2, put \(\eta=2^{-r_*}/16\), and choose the corresponding shortcode parameters \(\alpha,r_{\rm s}\), using a positive rational lower bound for \(\alpha\). Then choose a sufficiently large \(\ell\), as specified in Equation (33), and fix the corresponding latent data \((\mathcal V,K,C,\mu)\) and a splitting \(\mathcal V=K\oplus W\), with \(K=\mathbb F_2^\ell\).

Once the rational budgets are fixed, these choices are effective. For rational \(p_*\), the effective assertion of Lemma 2 supplies all the finite latent data, including a computable rational noise law, by a terminating deterministic construction. The effective bounds stated after Theorem 14 supply the rational choice of \(\alpha\) and the dimension thresholds, including \(m_0(\eta,\ell)\) after \(\ell\) has been fixed.

Next choose a cube \(k\ge8\) large enough for Proposition 24. Such a cube can be found by checking the estimates used in its proof. Write \(m=1+2k\) and \(\beta=k^{-2/3}\); since \(k\) is a cube, \(\beta\) is rational. Require \(m\ge m_0(\eta,\ell)\) and \[\frac{\alpha^2}{32}\,2^{(\ell-r_{\rm s})(m-r_{\rm s})} >(2r_{\rm s}+1)(\ell+m).\] The latter is a sufficient rational condition for the union bound in Lemma 18 to be less than one. For witness transfer in Lemma 20, require \[\frac14\left[ \left(1+\frac{|\mathcal V|-1}{3}\beta^2\right)^k-1\right] <\frac{\gamma_1^2}{(1+\alpha/4)^2},\] where \(\gamma_1\) is from Equation (41). The left-hand side is the square of the total-variation bound. For the final contradiction, require \[\left(1-\frac{\beta\,2^{-\dim W-r_{\rm s}}}{3600}\right)^k <\gamma,\] with \(\gamma\) from Proposition 16. All these conditions are rational and hold for sufficiently large cubes \(k\). Enumerating cubes until they hold therefore finds a suitable \(k\); the search cost depends only on the two prescribed errors and is incurred before the input formula is used.

Finally, with \(k\) fixed, choose a positive rational \[ \xi<\min\left\{\frac1{100},\frac{\varepsilon_0}{2kt}\right\}. \tag{58}\] Every choice depends only on the two prescribed errors. In particular, \(r_*\) is fixed before \(\ell\), the advice dimensions before \(k\), and \(k\) before the parity error \(\xi\).

Given a 3SAT formula, apply Theorem 11 and Lemma 12, and construct the matrix game \(H\) of Section 4. Proposition 24 gives \[\begin{array}{ll} \text{YES:}&\mathop{\mathrm{val}}(H)\ge1-d, \quad d=k\xi+p_*/2\le\varepsilon_0/t,\\[2pt] \text{NO:}&\mathop{\mathrm{val}}(H)\le99/100. \end{array}\] Apply Lemma 25 with \(\tau\) to obtain the unweighted simple bipartite game \(B\). It satisfies \[\begin{array}{ll} \text{YES:}&\mathop{\mathrm{val}}(B)\ge1-(d+\tau)/4,\\[2pt] \text{NO:}&\mathop{\mathrm{val}}(B)\le1-1/800, \end{array}\] where the NO bound is Equation (55). The final output is \(G=B^{\otimes t}\). Its NO value is at most \(\delta_0\le\delta\), by Equations (46) and (56). On a YES input, use a labeling of \(B\) coordinatewise. A union bound gives \[\mathop{\mathrm{val}}(G)\ge1-\frac{t(d+\tau)}4 \ge1-\varepsilon_0/2\ge1-\varepsilon.\]

The output has the claimed graph and constraint form. Its two vertex sets are the \(t\)-fold products of the two sides of \(B\). A pair of product vertices determines at most one edge in each coordinate, since \(B\) is simple, and hence at most one product edge. Independent uniform edge sampling is uniform on these product edges. The constraints of \(H\) are translations on \(K\), by Section 4; rounding and subdivision preserve them. The product of translations with offsets \(c_1,\ldots,c_t\) is translation by \((c_1,\ldots,c_t)\) on \(K^t=\mathbb F_2^{\ell t}\). This is the alphabet \(\mathbb F_2^s\) in the theorem, with \(s=\ell t\ge1\) fixed by the prescribed errors.

Proof. For the thesis’s common-arity convention (Raghavendra 2009, Definitions 7.2.1–7.2.2), identify \(D\) with a fixed \([q]\), and pad every predicate with ignored trailing arguments to a common positive arity, filling the added positions with a fixed variable of \(J\), which exists because \(A<B\). This leaves each applied payoff and its dependence set unchanged, hence preserves \(\operatorname{OPT}\) and the relaxation of (Raghavendra 2009, sec. 4.5). In that relaxation, each local distribution is over assignments to the variables on which its applied payoff actually depends. When emitting an occurrence, discard only the added trailing positions, retaining the original predicate from \(\Lambda\) and its weight.

Apply Raghavendra’s fixed-instance theorem (Raghavendra 2009, Theorem 7.9) with tolerance \(\eta/2\); see also (Raghavendra 2008, Theorem 1.1 and Lemma 2.3). The fixed witness and tolerance determine its strengthened Unique Games errors, so the formulation above and Theorem 1 supply its premise, with a fixed alphabet \([M]\). Its verifier instances have optimum greater than \(B-\eta/2\) in the YES case and at most \(A+\eta/2\) in the NO case.

We pass from the verifier’s probability weights to the stated rational weights. For this fixed invocation, the construction in (Raghavendra 2009, sec. 7.3.1 and 7.5) gives a local probability law \(\theta\) on a finite set \(\mathcal S\), after the alphabet \([M]\) is fixed. A record \(s\in\mathcal S\) specifies an applied predicate of \(J\), its \(a(s)\) ordered oracle-query strings in \(D^M\), and the positions filled by their replies. This law may depend on \(J,\eta,M\), but no varying input parameter enters it. Rational probability vectors are dense in this finite simplex, so fix \(\widehat\theta\in\mathbb Q_{\ge0}^{\mathcal S}\) with \[\sum_{s\in\mathcal S}\widehat\theta(s)=1, \qquad \delta:=\frac12\sum_{s\in\mathcal S} |\widehat\theta(s)-\theta(s)|<\frac{\eta}{2}.\] This rational table is fixed finite data of the reduction; its description length may depend on \(J,\eta,M\).

Let \(L_\Phi\) and \(V_\Phi\) be the left and right sides of the nonempty simple game supplied above, and let \(h\ge1\) be its common left degree. List the variables \(V_\Phi\times D^M\) used in Section 7.5 of the cited thesis. Its outer verifier chooses a uniform left vertex \(u\) and, independently for each oracle query, chooses a uniform neighbor of \(u\) and relabels the query string by that edge’s permutation. For each \(s\in\mathcal S\), \(u\in L_\Phi\), and ordered neighbor tuple in \(N(u)^{a(s)}\), emit the \(\Lambda\)-predicate prescribed by \(s\) on the resulting query variables. Fill all positions of any syntactic variable omitted from the test with the first listed output variable; the applied predicate is independent of such variables, so this leaves its value unchanged. Give the occurrence weight \[\frac{\widehat\theta(s)}{|L_\Phi|h^{a(s)}}.\] These weights are nonnegative rationals summing to one. Keeping equal occurrences separate gives \(|L_\Phi|\sum_{s\in\mathcal S}h^{a(s)}\) occurrences and \(|V_\Phi||D|^M\) variables. The local set and every \(a(s)\) are fixed, while the graph has polynomial size; hence this is a polynomial occurrence list. The explicit neighbor lists and edge permutations let us write it in polynomial time. Each weight has polynomial binary length: it can be represented with a fixed denominator multiplied by \(|L_\Phi|h^{a(s)}\).

For an assignment \(\sigma\), let \(g_\sigma(s)\in[0,1]\) be its conditional acceptance probability over these outer choices. The original and rationalized instances use the same variable set, and \[\bigl|\operatorname{val}_{\widehat\theta}(\sigma) -\operatorname{val}_{\theta}(\sigma)\bigr| =\left|\sum_{s\in\mathcal S} \bigl(\widehat\theta(s)-\theta(s)\bigr)g_\sigma(s)\right| \le\delta<\frac{\eta}{2}.\] Taking maxima gives the same bound for their optima. The imported gap therefore yields optimum at least \(B-\eta\) in the YES case and at most \(A+\eta\) in the NO case, as required. ◻

Proof. Proposition 30 constructs the stated finite instance from a simple strong-left Unique Games instance. It uses the local gap and analytic estimates of Guruswami et al. (Guruswami et al. 2011) and fixes the required game errors and degree conditions before the alphabet is chosen. Lemma 29 supplies that game from Theorem 1; composing the reductions proves the displayed gap for the original predicate \(\Pi\).

For a fixed \(r\in(\rho_\Pi,1]\), choose the positive error still smaller so that \(\varepsilon<(r-\rho_\Pi)/(1+r)\). Then \(r(1-\varepsilon)>\rho_\Pi+\varepsilon\), so an \(r\)-approximation would distinguish the two cases. ◻

Proof. Corollary 1.3 of (Chawla et al. 2006) gives the first three conclusions under its ordinary edge-value Unique Games hypothesis. For a requested factor \(C\), use its hardness statement at any fixed larger factor \(L\): a \(C\)-approximation would also be an \(L\)-approximation. To supply that hypothesis, orient the bipartite constraints of Theorem 1 left-to-right, renumber its fixed alphabet as \([d]\) with \(d=2^s\ge2\), and give its edges equal weights summing to one. Padding the smaller vertex side with isolated questions if needed preserves both value and polynomial size. The search-version qualification for Sparsest Cut is in Section 1.3 of the cited source.

For Correlation Clustering, the hard Multicut instances in (Chawla et al. 2006, sec. 2.1) have distinct antipodal demand pairs inside \(d\)-cubes, while the edges of the Multicut graph are cube edges or join different cubes. Here \(d\ge2\), unchanged by Lemma 1.5 of that source, so the demand pairs are nonedges. The transformation of Demaine, Emanuel, Fiat, and Immorlica (Demaine et al. 2006, Theorem 4.7 and Corollary 4.8) therefore creates no opposite-signed parallel edges. It preserves the optimum and converts every clustering into a multicut of no greater cost, so the same fixed-factor hardness transfers. ◻

Proof. We adapt the normalization and sequence construction of Khot and Regev (Khot and Regev 2008, Lemmas 3.3, 3.4, and 3.6). The extra copies of right vertices used below ensure that the final graph is simple.

Choose a multiple \(h\) of \(d\) with \[h\ge\max\{H,2\},\qquad \frac1h<\frac{\nu}{4}.\] For \((T)_h=T(T-1)\cdots(T-h+1)\), choose a fixed integer \(T\ge h\) such that \[p_{\mathrm{graph}}:=\frac{(T)_h}{T^h}>\frac34.\] Such a choice exists because \(1-(T)_h/T^h\le\binom h2/T\). Choose positive rationals \(\beta,\gamma,u\) and a positive integer \(L_2\) so that \[\beta<\frac{\nu}{4},\qquad h^2\gamma<\frac{\nu}{4},\qquad (h+1)u<\frac{\zeta}{2},\qquad \frac1{L_2}<\min\left\{\frac{\beta\gamma}{2}, \frac{\zeta}{2h}\right\}.\] Finally choose positive rational \(\gamma_0,\zeta_0<1/2\) with \[2\gamma_0<\frac{\beta\gamma}{2}, \qquad \sqrt{2\zeta_0}<u.\] All these choices precede the invocation of Theorem 1 with completeness error \(\zeta_0\) and soundness error \(\gamma_0\).

Write its output as \(\Phi_0=(X_0,Y,E_0)\), orienting each permutation left-to-right and renumbering the fixed alphabet as \([R]\). Put \(M_0=|E_0|>0\), give each edge weight \(1/M_0\), and let \(w_x\) be the total incident weight at \(x\). Simplicity gives one permutation at each pair of positive weight. Create \[n_x=\lfloor 2|X_0|w_x\rfloor\] copies of \(x\), each with local edge weights \(w_{xy}/w_x\). Only vertices with \(w_x>0\) have copies. If \(X_1\) is the copy set, then \[|X_0|\le |X_1|=\sum_x n_x\le2|X_0|,\] and the incident weight at each copy is one.

Here and below a local satisfied weight uses the labels at that left vertex and at the shared right vertices. Given any labeling of the copy game, keep the right labels and give all copies of each \(x\) a label that maximizes their common local objective. The corresponding labeling \(L\) of \(\Phi_0\) satisfies \[\sum_{x'\in X_1} w_{\mathrm{sat}}(x') \le \sum_{x:n_x>0}\frac{n_x}{w_x}w_{\mathrm{sat},L}(x) \le 2|X_0|\,w_{\mathrm{sat},L}(\Phi_0).\] Consequently the copy game’s normalized value is at most \(2\gamma_0\) on a NO input. On a YES input, lift a labeling of \(\Phi_0\) with unsatisfied weight at most \(\zeta_0\). The same calculation for unsatisfied weight gives mean local loss at most \(2\zeta_0<u^2\). Markov’s inequality leaves more than a \(1-u\) fraction of \(X_1\) with local satisfied weight at least \(1-u\).

To remove the weights, put \(\alpha=L_2|Y|\). At each \(x\in X_1\), write \(\widetilde w_{xy}\) for its normalized local weights. Choose one neighbor \(y_0\) of positive local weight, round \(\alpha\widetilde w_{xy}\) down for every \(y\ne y_0\), and assign the remaining occurrences to \(y_0\). All occurrences at a pair retain that pair’s permutation. This gives an unweighted multigraph \(\Phi_{\mathrm{occ}}\) of left degree \(\alpha\). For any subset of the neighbors, the difference between its old weight and its new occurrence fraction has magnitude at most \(|Y|/\alpha=1/L_2\): sum the rounding losses over the subset if it omits \(y_0\), and over its complement otherwise. This applies to the satisfied subset for every labeling. Hence \[ \mathop{\mathrm{val}}(\Phi_{\mathrm{occ}})\le 2\gamma_0+\frac1{L_2}<\beta\gamma \quad\text{on a NO input}. \tag{59}\] On a YES input, the labeling above has satisfied occurrence fraction at least \(1-a\), where \(a=u+1/L_2\), at more than a \(1-u\) fraction of \(X_1\).

Index the \(\alpha\) occurrences at \(x\) by \(j\), with right endpoint \(y_j\) and permutation \(\pi_j\). Replace each \(y\in Y\) by \((y,t)\), \(t\in[T]\), and replace occurrence \(j\) by all \(T\) occurrences from \(x\) to \((y_j,t)\) with permutation \(\pi_j\). Call the resulting left-\(\alpha T\)-regular multigraph \(\Phi_{\mathrm{tag}}\). For any labeling of \(\Phi_{\mathrm{tag}}\), keep its left labels and, independently for each original \(y\), give \(y\) the label of a uniformly chosen copy \((y,t)\). The expected edge value in \(\Phi_{\mathrm{occ}}\), counting its occurrences, is exactly the given edge value in \(\Phi_{\mathrm{tag}}\). Thus \[ \mathop{\mathrm{val}}(\Phi_{\mathrm{tag}})\le\mathop{\mathrm{val}}(\Phi_{\mathrm{occ}})<\beta\gamma \quad\text{on a NO input}. \tag{60}\] The tag-independent lift of the YES labeling preserves every local satisfied fraction.

Consider the full sequence graph whose left vertices are \[\bigl(x,(j_1,t_1),\ldots,(j_h,t_h)\bigr), \qquad j_i\in[\alpha],\quad t_i\in[T],\] with position \(i\) joined to \((y_{j_i},t_i)\) by \(\pi_{j_i}\). This is the sequence construction of Khot and Regev; its left vertex identifier includes the entire ordered occurrence sequence. We record the soundness estimate in a form that permits the left label to depend on that entire sequence. Each \(x\) contributes exactly \((\alpha T)^h\) full sequence vertices, all of degree \(h\). Thus the uniform edge value is the average satisfied fraction over a uniform \(x\), an ordered \(h\)-tuple of independent uniform occurrences at \(x\), and a uniform position in that tuple.

Fix arbitrary right labels in \(\Phi_{\mathrm{tag}}\). Each occurrence at \(x\) determines the unique left label that satisfies it. Let \(p_x(\ell)\) be the fraction determining label \(\ell\). The \(p_x(\ell)\) sum to one, and choosing the best left label at each \(x\) gives \[\mathbb E_x\max_\ell p_x(\ell)\le\mathop{\mathrm{val}}(\Phi_{\mathrm{tag}})<\beta\gamma.\] Fewer than a \(\beta\) fraction of \(x\) therefore have \(\max_\ell p_x(\ell)\ge\gamma\). At every other \(x\), the probability that two labels determined by \(h\) independent occurrences agree is at most \[\binom h2\sum_\ell p_x(\ell)^2 \le \binom h2\max_\ell p_x(\ell)<h^2\gamma.\] If no two determined labels agree, any label of the sequence vertex satisfies at most one of its \(h\) edges. On the remaining sequences its satisfied fraction is at most one. Averaging first over sequences and then over \(x\), and using \(1/h+h^2\gamma<1\), bounds the full sequence graph’s value by \[ s:=\beta+\frac1h+(1-\beta)h^2\gamma<\frac{3\nu}{4}. \tag{61}\] The estimate holds for every choice of the right labels and every sequence-dependent choice of left labels.

Retain only sequence vertices for which \(t_1,\ldots,t_h\) are pairwise distinct. For each \(x\) and each base sequence \((j_1,\ldots,j_h)\), exactly \((T)_h\) tag sequences remain. Each \(x\) thus contributes \(\alpha^h(T)_h\) retained vertices, a fraction \(p_{\mathrm{graph}}\) of its full set. The \(h\) right neighbors of each retained vertex are distinct because their tags are distinct. Different occurrence sequences remain different left vertices, so this retained graph is simple and has common left degree \(h\).

Give each sequence vertex based at \(x\) the old label of \(x\), and keep the tag-independent right labels. For this lifted YES labeling, satisfaction at position \(i\) depends only on \(j_i\). Conditioning the tags to be distinct leaves the base occurrence sequence independent and uniform. If the satisfied fraction at \(x\) in \(\Phi_{\mathrm{occ}}\) is \(f_x\), exactly an \(f_x^h\) fraction of its retained sequence vertices are strongly satisfied. Since every \(x\) contributes equally, the strongly satisfied fraction is at least \[(1-u)(1-a)^h \ge 1-u-ha =1-(h+1)u-\frac h{L_2}>1-\zeta.\] Here \(0<a<1\) follows from the parameter choices.

For NO, extend any labeling of the retained graph to the full graph by giving discarded left vertices arbitrary labels and keeping all right labels. All left degrees are \(h\), so its full edge value is at least \(p_{\mathrm{graph}}\) times its retained edge value. By (61), the latter is at most \[\frac{s}{p_{\mathrm{graph}}}<\frac{3\nu/4}{3/4}=\nu.\] This extension permits arbitrary dependence of the retained left labels on their tags.

All the operations are finite and deterministic. If \(N\) bounds the explicit size of \(\Phi_0\), then \(|X_1|=O(N)\) and \(\alpha=L_2|Y|=O(N)\). The retained graph has \(|X_1|\alpha^h(T)_h=O(N^{h+1})\) left vertices and \(h\) edges per left vertex. Its identifiers and the rational arithmetic used for rounding have polynomial bit length, and its permutation tables use the fixed alphabet inherited from \(\Phi_0\). This proves the claimed polynomial bound and completes the reduction. ◻

Proof. The explicit increasing-tuple construction in (Guruswami et al. 2011, Theorem 11.1, Definition 11.2, and the proof of Theorem 2.5), applied to \(P_0\), gives a finite instance \(J^*\) with \(\operatorname{opt}_q(J^*)\le\rho_\Pi+\eta\) and a linear order satisfying every constraint. Its distribution uses only uniform choices from finite sets, so its weights are rational. Its tuple positions lie in successive disjoint intervals and are therefore distinct.

Use the finite-copy smoothing from the proof of (Guruswami et al. 2011, Lemma 8.9), specialized to this complete order. Take \(L\) disjoint copies of \(J^*\), each of weight \(1/L\), and place their complete orders consecutively in an order \(\sigma:U\to[m]\), where \(m=L|U^*|\). The resulting instance \(J\) still has \(\operatorname{opt}_q(J)\le\rho_\Pi+\eta\), since the value of any \(q\)-assignment is the average of its values on the copies. Choose \(L\) and a positive rational \(s_0<1\) so that \(1/L+s_0<\eta\). Define a random assignment \(X:U\to[m]\) as follows: with probability \(1-s_0\), choose a uniform cyclic shift of the ranks of \(\sigma\); with probability \(s_0\), assign the variables independently and uniformly from \([m]\).

Each variable is uniform in either part of the mixture. A cyclic cut can split at most one of the \(L\) consecutive copies, so every shift has payoff at least \(1-1/L\). The mixture’s payoff is therefore at least \((1-s_0)(1-1/L)>1-\eta\). Let \(\mu_c\) be its restriction to the variables of \(c\). If \(n_c(x)\) is the number of the \(m\) cyclic shifts with restriction \(x\), then \[\mu_c(x)=(1-s_0)\frac{n_c(x)}m+\frac{s_0}{m^k}.\] These atoms are rational and exceed \(\alpha:=s_0/(2m^k)\). The denominator \(m^k\) is valid because the variables in \(c\) are distinct.

Finally regard the finite mixture as a probability space and take \(I=\mathbf1\) and \(b_{u,j}=\mathbf1_{\{X(u)=j\}}\) in its \(L^2\) space. Uniform marginals, disjoint events for different labels of one variable, and restrictions to each \(c\) give all the displayed Gram identities. This constructs the required feasible data for this particular local instance. ◻

Proof. This is the dimension-uniform form of (Guruswami et al. 2011, Lemmas 3.4 and 3.5) needed here. For \(H=T_{1-\kappa}F\), the Fourier formula gives \[\|T_{1-2\kappa}F\|_2^2 \le \operatorname{Stab}_{1-\kappa}(H),\] where \(\operatorname{Stab}_\theta(H) =\sum_\sigma\theta^{|\sigma|}\widehat H(\sigma)^2\). Indeed, \((1-\kappa)^3-(1-2\kappa)^2 =\kappa(1-\kappa-\kappa^2)>0\). Each full coordinate influence bound for \(H\) implies the corresponding low-degree influence bound in Theorem 4.4 of Mossel, O’Donnell, and Oleszkiewicz (Mossel et al. 2010). Apply that theorem with product dimension \(R\), one-coordinate atom bound \(1/m\), and correlation \(1-\kappa\). For all sufficiently small \(t\), it gives \[\operatorname{Stab}_{1-\kappa}(H) \le \Gamma_{1-\kappa}(\mu) +C\frac{\log(2m)}{\kappa} \frac{\log\log(1/t)}{\log(1/t)}.\] The cutoff and this error are independent of \(R\) and \(\mu\). Here \(\Gamma_\theta(\mu)\) is the Gaussian halfspace noise stability of a set of Gaussian measure \(\mu\).

For fixed \(\kappa\), Theorem B.5 of the same source gives \(\Gamma_{1-\kappa}(\mu)=\mu^{2/(2-\kappa)+o(1)}\) as \(\mu\downarrow0\). Since \[\frac{2}{2-\kappa}-\left(1+\frac{\kappa}{2}\right) =\frac{\kappa^2}{2(2-\kappa)}>0,\] there is a cutoff \(\mu_0(\kappa)>0\), independent of \(m,R\), below which \(\Gamma_{1-\kappa}(\mu)\le\mu^{1+\kappa/2}\). This proves the corresponding squared \(L^2\) bound for both \(F\) and \(G\), with an error \(r_c^{m,\kappa}(t)\to0\) independent of the stated variables. Choose a cutoff \(t_0<e^{-e}\) within the range of the displayed bound, use its nonnegative error for \(0<t<t_0\), and set \(r_c^{m,\kappa}(t)=1\) for \(t\ge t_0\). The latter range follows trivially from the product being at most one. Cauchy–Schwarz under any coupling with the specified marginals proves (67). ◻

Proof. This is the simplex-valued estimate of (Guruswami et al. 2011, Lemma 10.5), with its sufficient scalar influence bounds and their dependence made explicit. Put \(H=T_{1-\lambda}F\). Independence of the noise between positions and multilinearity turn the left side of (69) into \[ \mathbb E_c\mathbb E_{Z\sim\mu_c^{\otimes R}} P_0^{\mathrm{ml}}\bigl(H(Z_1),\ldots,H(Z_k)\bigr). \tag{70}\]

For each coordinate, the integral ensemble consists of the indicators \(\mathbf1_{\{X_i=j\}}\) under \(\mu_c\); its atoms have probability greater than \(\alpha\). The common Gram data (65) supply one Gaussian ensemble for all variables of \(J\) with the same first and second moments on every constraint, as in (Guruswami et al. 2011, Lemma 10.4). Explicitly, for a standard Gaussian vector \(g\) in the span of the Gram vectors, the variables \[G_{u,j}=\langle I,b_{u,j}\rangle+ \langle b_{u,j}-\langle I,b_{u,j}\rangle I,g\rangle\] have those moments. Use independent copies of this ensemble in the \(R\) coordinates. Each \(H^j\) is evaluated on these ensembles through its multilinear product expansion; equivalently, express an orthonormal basis on \([m]\) as linear combinations of the symbol indicators and use the same polynomial for the integral and Gaussian ensembles.

For a fixed \(c\), let \(\mathcal T_\theta^c\) retain each whole coordinate tuple with probability \(\theta\) and otherwise resample it from \(\mu_c\). Uniform one-position marginals give, componentwise, \[\mathcal T_{1-\lambda}^c[F^j(Z_i)] =(T_{1-\lambda}F^j)(Z_i)=H^j(Z_i).\] Thus these are the smoothed components required by the invariance theorem on the product of the tuple ensembles. The same marginals give the exact influence identity below; the superscript indicates the product measure used to compute influence: \[ \operatorname{Inf}^{\mu_c^{\otimes R}}_\ell \bigl(H^j(Z_i)\bigr) = \operatorname{Inf}^{[m]^R}_\ell(H^j). \tag{71}\] Indeed, conditioning on every coordinate tuple except the \(\ell\)th leaves the \(\ell\)th symbol at position \(i\) uniform, and the other symbols at that position have the uniform product law. For a vector, influence is the sum of its component influences (Isaksson and Mossel 2009, Definition 2.6). Thus the vector \((H^j(Z_i))_{i\in[k],j\in[q]}\) has each coordinate influence at most \(kqt\); each component has variance at most one.

For the remaining tail hypothesis, let \((F^j(Z_i))_S\), \(S\subseteq[R]\), be the Hoeffding components on the tuple product \(\mu_c^{\otimes R}\), and let the superscript \(>d\) retain the terms with \(|S|>d\). The tuple-noise identity above multiplies component \(S\) by \((1-\lambda)^{|S|}\). Since the unsmoothed \(F^j\) takes values in \([0,1]\), for every real \(d>0\), \[\begin{aligned} \operatorname{Var}\bigl((H^j(Z_i))^{>d}\bigr) &=\sum_{|S|>d}(1-\lambda)^{2|S|} \bigl\|(F^j(Z_i))_S\bigr\|_2^2\\ &\le (1-\lambda)^{2d}\operatorname{Var}(F^j(Z_i)) \le (1-\lambda)^{2d}. \end{aligned}\] All norms and variances here use \(\mu_c^{\otimes R}\). This supplies the tail bound in (Isaksson and Mossel 2009, Theorem 3.6). These are sufficient hypotheses for the vector-valued invariance estimate stated in (Guruswami et al. 2011, Theorem 10.1).

Let \(\mathsf p:\mathbb R^q\to\mathcal S_q\) be Euclidean projection. It is nonexpansive. The function \[\Psi(x_1,\ldots,x_k)= P_0^{\mathrm{ml}}(\mathsf p(x_1),\ldots,\mathsf p(x_k))\] is Lipschitz with constant at most \(\sqrt{kq}\): on the simplex, telescoping the positions bounds the payoff difference by \(\sum_i\|x_i-y_i\|_1\), and projection and Cauchy–Schwarz give the claim. Apply the cited invariance estimate to this function, separately for each \(c\), with vector dimension \(kq\) and influence threshold \(kqt\). Its displayed error is at most \[r_s(kqt),\qquad r_s(u)=C_{kq}\sqrt{kq}\, u^{\lambda/(18\log(1/\alpha))}.\] In particular the error is independent of \(R\).

On the integral ensemble, \(H(Z_i)\in\mathcal S_q\), so \(\Psi\) equals the payoff in (70). On the common Gaussian ensemble, project \(H(G_u)\) to \(\mathcal S_q\) for every \(u\in U\), and independently draw one \(q\)-label for each \(u\) with those probabilities. This is one random assignment of \(J\). The variables in every local tuple are distinct, so its conditional expected payoff at that tuple is the multilinear payoff \(\Psi\). Every realized assignment has value at most \(\operatorname{opt}_q(J)\). Averaging the invariance comparisons over \(c\) proves (69). ◻

Proof of Proposition 30. We first derive estimates that hold for every \(R\), then choose their numerical parameters independently of \(R\). Fix for now \(0<\kappa<1/2\), \(q\) with \(1/q\le\mu_0(\kappa)\), and local data from Lemma 31. Use the local experiment of Lemma 33 with the actual resampling probability \(\lambda=2\kappa\). Also fix auxiliary constants \(0<t<1/(kq)\) and \(\chi>0\).

For an input graph \(\Phi\), let \(\pi_{a\to b}\) denote the permutation on edge \(ab\). Its action on strings is fixed by \[(\pi_{a\to b}z)_{\pi_{a\to b}(\ell)}=z_\ell \qquad(\ell\in[R]).\] The output variable set will be \(\mathcal V=B\times[m]^R\). Consider the following independent neighbor experiment: choose \(a\) uniformly from \(A\), choose \(b_1,\ldots,b_k\) independently and uniformly from \(N(a)\), and independently perform the local experiment, obtaining \(\widetilde Z_1,\ldots,\widetilde Z_k\). Its raw output positions are \[ w_i=(b_i,\pi_{a\to b_i}\widetilde Z_i)\in\mathcal V. \tag{72}\] For any rank map \(f:\mathcal V\to\mathbb Z\), define \[V(f)=\mathbb E\, \overline{P_0}\bigl(f(w_1),\ldots,f(w_k)\bigr), \qquad V_a(f)=\mathbb E[ \overline{P_0}(f(w_1),\ldots,f(w_k))\mid a].\] The bounded payoff (62) is used even if the experiment repeats an output ID. We will obtain a lower bound for one coarse rank map and an upper bound for every injective order, then transfer both bounds to distinct-variable constraints.

Suppose a labeling \(L\) strongly satisfies at least \(1-\zeta\) of the left vertices. Define the coarse rank map \(f(b,z)=z_{L(b)}\). At every strongly satisfied \(a\) and every neighbor \(b\), \[f(b,\pi_{a\to b}z)=z_{\pi_{a\to b}^{-1}(L(b))}=z_{L(a)}.\] Thus all \(k\) positions read the same label coordinate, for every choice of neighbors. With probability \((1-2\kappa)^k\) none of these \(k\) symbols is resampled; conditional on that event their tuple has law \(\mu_c\). Nonnegativity of the payoff gives \[ V(f)\ge (1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}. \tag{73}\]

For soundness fix an injective order \(O:\mathcal V\to[|\mathcal V|]\). At a fixed \(a\), its local set \(N(a)\times[m]^R\) has exactly \(M=hm^R\) distinct IDs. Sort this set by \(O\) and divide the sorted list into \(q\) consecutive blocks \(C_{a,1},\ldots,C_{a,q}\) of size \(M/q\). These sizes are integers because \(q\mid h\). Each block is the intersection of the local set with an interval of global ranks. Define \[ F_a^j(z)=\frac1h\sum_{b\in N(a)} \mathbf1_{\{(b,\pi_{a\to b}z)\in C_{a,j}\}}, \qquad F_a=(F_a^1,\ldots,F_a^q). \tag{74}\] For every \(z\), \(F_a(z)\in\mathcal S_q\). Each edge permutation is a bijection on strings, so \[ \mathbb E_z F_a^j(z)=\frac{|C_{a,j}|}{hm^R}=\frac1q. \tag{75}\]

For any interval \(I\) of integer ranks put \[F_a^I(z)=\frac1h\sum_{b\in N(a)} \mathbf1_{\{O(b,\pi_{a\to b}z)\in I\}}.\] Call \(a\) pseudorandom at threshold \(t\) if \(\operatorname{Inf}_\ell(T_{1-\kappa}F_a^I)\le t\) for every \(I\) and every \(\ell\in[R]\). At such an \(a\), this bound holds for each block function \(F_a^j\).

Let \(j_a(w)\) be the block index of a local ID \(w\). Conditional on the local query strings, independence of the neighbor choices gives the exact identity \[ \mathbb E_{b_1,\ldots,b_k} \overline{P_0}\bigl(j_a(w_1),\ldots,j_a(w_k)\bigr) = P_0^{\mathrm{ml}}\bigl(F_a(\widetilde Z_1),\ldots, F_a(\widetilde Z_k)\bigr). \tag{76}\] The identity includes outcomes with equal neighbors. Further smoothing decreases the block influences, so \(\operatorname{Inf}_\ell(T_{1-2\kappa}F_a^j)\le t\). Lemma 33, applied to the single function \(F_a\), bounds the expected coarse payoff in (76) by \(\operatorname{opt}_q(J)+r_s(kqt)\).

When the \(k\) coarse ranks are distinct, their induced permutation is the one induced by the fine ranks \(O(w_i)\). Otherwise the two payoffs differ by at most one. This also covers a repeated output ID, which necessarily produces a coarse tie. For two positions \(i\ne i'\), independence of their noise and neighbor choices gives their coarse tie probability as \[\sum_{j=1}^q \mathbb E_c\mathbb E_{Z\sim\mu_c^{\otimes R}} \bigl[ (T_{1-2\kappa}F_a^j)(Z_i) (T_{1-2\kappa}F_a^j)(Z_{i'}) \bigr].\] Conditional on \(c\), both strings have uniform product marginals. Their correlation is permitted by Lemma 32. Use that lemma with the fixed mean \(1/q\) from (75), and write \(r_c=r_c^{m,\kappa}\). The last display is at most \(q^{-\kappa/2}+q r_c(t)\). A union bound over pairs therefore gives, at every pseudorandom \(a\), \[ V_a(O)\le S_{\mathrm{loc}}:=\operatorname{opt}_q(J) +\binom{k}{2}\bigl(q^{-\kappa/2}+q r_c(t)\bigr) +r_s(kqt). \tag{77}\]

We next turn an excess over this bound into a labeling of \(\Phi\). For each \(b\in B\), restrict \(O\) to \(\{b\}\times[m]^R\) and compress its ranks to obtain a strict order \(o_b\) of \([m]^R\). Let \[\mathcal L_b=\left\{\ell\in[R]: \operatorname{Inf}_\ell \bigl(T_{1-\kappa}\mathbf1_{\{o_b(z)\in I\}}\bigr)>t/2 \text{ for some rank interval }I\right\}.\] The few-influential-coordinates lemma (Guruswami et al. 2011, Definition 4.2 and Lemma 4.3) gives \[ |\mathcal L_b|\le\frac{400}{\kappa(t/2)^3} =\frac{3200}{\kappa t^3}. \tag{78}\] This bound is uniform in \(R\).

If \(a\) is not pseudorandom, choose one witnessing interval \(I_a\) and coordinate \(\ell_a\) with \(\operatorname{Inf}_{\ell_a}(T_{1-\kappa}F_a^{I_a})>t\). Noise commutes with coordinate permutations and averaging, and influence is a convex squared norm. Hence \[ \operatorname{Inf}_{\ell_a}(T_{1-\kappa}F_a^{I_a}) \le\frac1h\sum_{b\in N(a)} \operatorname{Inf}_{\pi_{a\to b}(\ell_a)} \left(T_{1-\kappa} \mathbf1_{\{O(b,z)\in I_a\}}\right). \tag{79}\] Each term is at most one. An average greater than \(t\) forces more than a \(t/2\) fraction of the terms to exceed \(t/2\). The restriction of a global-rank interval to one right code is an interval of its relative order, so these neighbors satisfy \(\pi_{a\to b}(\ell_a)\in\mathcal L_b\).

Give each such \(a\) label \(\ell_a\), and label every other left vertex arbitrarily. Independently at each right vertex with \(\mathcal L_b\ne\varnothing\), choose one uniform label from \(\mathcal L_b\); use any label when the set is empty. By (78), the expected satisfied fraction among the edges at each nonpseudorandom \(a\) is greater than \[\frac t2\,\frac{\kappa t^3}{3200} =\frac{\kappa t^4}{6400}.\] One random right labeling is used for all left vertices. Linearity of expectation and the common left degree identify the resulting average with the ordinary uniform edge fraction.

If \(V(O)>S_{\mathrm{loc}}+\chi\), more than a \(\chi\) fraction of left vertices are nonpseudorandom: if that fraction is \(g\), the bound \(0\le V_a(O)\le1\) and (77) give \(V(O)\le(1-g)S_{\mathrm{loc}}+g\le S_{\mathrm{loc}}+g\). The preceding decoder would then give a labeling of edge value greater than \(\chi\kappa t^4/6400\). Consequently \[ \mathop{\mathrm{val}}(\Phi)\le\nu<\frac{\chi\kappa t^4}{6400} \quad\Longrightarrow\quad V(O)\le S_{\mathrm{loc}}+\chi\quad\text{for every injective }O. \tag{80}\]

It remains to turn the independent experiment into strict ordering constraints. Let \(D\) be the event that \(b_1,\ldots,b_k\) are distinct. For \(h\ge k\), \[ p_D:=\Pr(D)=\frac{(h)_k}{h^k},\qquad \delta_h:=1-p_D\le\frac{\binom{k}{2}}h. \tag{81}\] The probability is the same at every \(a\), and \(D\) is independent of the local experiment. Conditional on \(D\), \(a\) remains uniform and its ordered distinct neighbor tuple is uniform among its \((h)_k\) possibilities. All output IDs are then distinct because their first coordinates \(b_i\) differ. Let \(I_0\) denote this finite weighted distribution of strict \(P_0\) constraints, and write \(\mathop{\mathrm{OPT}}_{P_0}(I_0)\) for its maximum strict payoff.

Let \(V_D(f)\) denote the expected tie-extended payoff after this conditioning, and use \(V_{\neg D}(f)\) for conditioning on its complement. For any rank map \(f\), coarse or injective, \[ V(f)=p_DV_D(f)+(1-p_D)V_{\neg D}(f), \qquad |V_D(f)-V(f)|\le\delta_h, \tag{82}\] because all payoffs lie in \([0,1]\). Apply this first to the coarse map in (73). Within each finite fiber of that map, choose one uniform random permutation of the distinct IDs, independently between fibers, and concatenate the fibers in rank order. On every conditioned tuple, restriction of these permutations to its IDs is uniform within each tied rank class. Thus the expected strict \(P_0\)-payoff of this one random global order equals \(V_D(f)\). Some global order attains at least that value. For soundness, an injective \(O\) has distinct ranks on every conditioned tuple, so its tie-extended payoff there is its strict \(P_0\)-payoff. Equations (73), (80), and (82) therefore give the strict bounds \[ \begin{aligned} \mathrm{YES}:\quad& \mathop{\mathrm{OPT}}_{P_0}(I_0)\ge(1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}-\delta_h,\\ \mathrm{NO}:\quad& \mathop{\mathrm{OPT}}_{P_0}(I_0)\le S_{\mathrm{loc}}+\chi+\delta_h \quad\text{if }\nu<\chi\kappa t^4/6400. \end{aligned} \tag{83}\] These bounds are for the conditioned \(P_0\) tuples. Applying (63) makes every occurrence use the original predicate \(\Pi\) with exactly the same values. Call this emitted instance \(I\).

We now make the choices for the prescribed \(\delta\). Choose a positive rational \(\eta\) with \(10\eta<\delta\), and a rational \(0<\kappa<1/2\) with \(2\kappa k<\eta\). Put \(K=\binom{k}{2}\). Choose an integer \(q\) so large that \[\frac1q\le\mu_0(\kappa),\qquad Kq^{-\kappa/2}<\eta.\] Choose the data \(J,m,\alpha\) from Lemma 31 at error \(\eta\). The two analytic error functions now have fixed parameters and are uniform in \(R\). Choose a positive rational \(t<1/(kq)\) so small that \[Kq r_c(t)<\eta,\qquad r_s(kqt)<\eta.\] Set \(\chi=\eta\). Choose positive rationals \(\zeta,\nu<1\) with \[\zeta<\eta,\qquad \nu<\frac{\eta\kappa t^4}{6400},\] and choose an integer \(H\ge\max\{k,q\}\) with \(K/H<\eta\). These choices depend only on \(k,\Pi,\delta\). In particular, they precede both the choice of \(h\) in Lemma 29 and the alphabet supplied by Theorem 1.

For every \(h\ge H\), \(\delta_h<\eta\). The local gap (64), Bernoulli’s inequality, and (83) give \[\mathrm{YES}:\quad \mathop{\mathrm{OPT}}_\Pi(I)\ge1-\zeta-2\kappa k-\eta-\delta_h >1-4\eta>1-\delta,\] whereas (77) gives \[\mathrm{NO}:\quad \mathop{\mathrm{OPT}}_\Pi(I)\le S_{\mathrm{loc}}+\chi+\delta_h <\rho_\Pi+6\eta<\rho_\Pi+\delta.\] This proves the numerical claims simultaneously for every \(R\).

Finally we specify the encoded transformation. Once \(R\) is fixed, the choice of \(c\), the product \(\mu_c^{\otimes R}\), and the independent rational \(2\kappa\)-noise form one fixed finite rational law \(\theta_R\) on local outcomes \(\xi\). These are the actual local outcomes above; the Gaussian variables used for the analytic comparison are not part of the output. Renumber \(B\) by \([|B|]\) and explicitly list \(\mathcal V=B\times[m]^R\). For each \(a\in A\), each ordered distinct neighbor tuple, and each \(\xi\in\operatorname{supp}\theta_R\), list the tuple in (72), permuted by (63), with weight \[ \frac{\theta_R(\xi)}{|A|(h)_k}. \tag{84}\] The weights sum to one and are nonnegative rationals. Every listed tuple has distinct IDs; the same tuple may occur in several entries. There are \(|B|m^R\) variables and at most \(|A|(h)_k|\operatorname{supp}\theta_R|\) entries. For fixed \(k,m,R,\theta_R\), these counts are polynomial in the explicit graph size, even when \(h\) varies. A fixed common denominator for \(\theta_R\) shows that each weight has \(O(\log|A|+k\log h)\) bits plus a fixed constant. The IDs have \(O(\log|B|)\) bits plus a fixed constant. Exact enumeration of these entries is therefore deterministic and polynomial for fixed \(R\), as asserted. ◻