Proof strategy

The reduction first constructs weighted comparisons between bits using Gaussian-sampled queries. A satisfying source instance admits bits of total comparison cost at most \(4\), whereas an unsatisfiable instance forces cost greater than an arbitrarily prescribed constant \(J\). The graph construction then realizes each failed comparison by exactly one uncut edge. The main work is obtaining this comparison gap with constants chosen before the label alphabet.

Relation to earlier methods

The parity-equation starting point belongs to the PCP approach to hardness of approximation: a locally checked proof gives a finite constraint system with a gap between satisfiable and unsatisfiable inputs. Håstad’s construction provides the near-satisfiable parity gap used here, while the parallel repetition theorems of Raz and Holenstein amplify the corresponding two-player game (Håstad 2001; Raz 1998; Holenstein 2009). Neither step assumes Unique Games. In particular, the completeness error is positive and is selected only after the repetitions have been fixed.

Our bit proofs use the long code and folding of Bellare, Goldreich and Sudan (Bellare et al. 1998), which also underlie Håstad’s Fourier analysis. Khot and Safra use smooth equation–variable games and decode short label lists from large Fourier coefficients (Khot and Safra 2013, secs. 3.2–3.4 and 5.2). Shared linear advice and coordinates on which that advice vanishes appear in Khot, Minzer and Safra (Khot et al. 2025, secs. 3.3–3.4); a related shared-subspace formulation appears in Dinur et al. (Dinur et al. 2025, Lemma 5.4). Our outer-game proofs retain this mechanism but establish the precise hinted soundness and joint approximation estimates needed by a decoder that depends on its shared background.

The analytic tools also have established precedents. The Gaussian sign identity is the random-hyperplane calculation of Goemans and Williamson (Goemans and Williamson 1995), and Gaussian smoothing and Hermite expansions are standard in noise-stability analysis (Mossel et al. 2010). The box estimate uses the iterated Cauchy–Schwarz mechanism in Gowers’s hypergraph arguments (Gowers 2007). We prove the identities and inequalities used here. The additional argument is the extraction of an odd one-entry coefficient from an arbitrary bit proof, uniformly in its alphabet, and its transfer through a random affine map when the remaining coefficients depend on the background.

Affine alphabets and odd characters

For an affine space \(A\), let \(D(A)\) be the vector space of affine functions \(A\to\mathbb F_2\), including constants. If \(A\) has dimension \(r\), then \(D(A)\) has dimension \(r+1\). Write \(1\in D(A)\) for the constant-one function. A frequency is an element \(\alpha\) of the linear dual \(D(A)^*\), with character \(\chi_\alpha(b)=(-1)^{\alpha(b)}\). Call \(\alpha\) odd if \(\alpha(1)=1\).

For a real function \(v\) on a finite binary vector space \(W\), write \[\widehat v(\alpha)=\mathbb E_{w\in W}v(w)(-1)^{\alpha(w)},\qquad v(w)=\sum_{\alpha\in W^*}\widehat v(\alpha)(-1)^{\alpha(w)}.\] Character orthogonality gives Parseval’s identity \(\sum_\alpha\lvert\widehat v(\alpha)\rvert^2=\mathbb Ev^2\). If \(T:W'\to W\) is linear, each character of \(v\) pulls back to its image under \(T^*\); coefficients with the same image add. Injectivity and surjectivity of \(T\) are unnecessary. We will use the identity \[ \sum_\alpha\lvert\widehat v(\alpha)\rvert^4 =\mathbb E_{a,b,c\in W}v(a)v(b)v(c)v(a+b+c). \tag{1}\] Indeed, expansion of the four factors and averaging over the three independent points force all four frequencies to agree.

Gaussian identities

We recall the Fourier–Hermite identities used in Gaussian noise-stability analysis (Mossel et al. 2010, sec. 4.1 and 5), with proofs of the needed forms. Let \(\gamma_d\) be standard Gaussian probability measure on \(\mathbb R^d\). The normalized Hermite polynomials \(H_j\) are specified by \[e^{tz-t^2/2}=\sum_{j\ge0}H_j(z)\frac{t^j}{\sqrt{j!}}.\] Gaussian integration of the product of two generating functions proves their orthonormality. Their products \(\psi_I(c)=\prod_x H_{I_x}(c_x)\) form an orthonormal basis of \(L^2(\gamma_d)\). For completeness, if a function is orthogonal to all these polynomials, its Gaussian-weighted exponential transform has every Taylor coefficient zero. Cauchy–Schwarz makes that transform entire in each variable; its restriction to imaginary arguments is the Fourier transform of an integrable function, which is therefore zero. Thus the original function is zero almost everywhere.

Differentiating the generating function gives \(H_j'=\sqrt j H_{j-1}\). Consequently, for a function with square-integrable weak gradient, \[ \int\lVert\nabla F\rVert^2\,\mathrm d\gamma_d =\sum_I |I|\lvert\widehat F(I)\rvert^2, \qquad |I|=\sum_x I_x. \tag{2}\] One first proves this for polynomials, and then passes to the Hermite partial sums and weak derivatives. In the smoothed functions used below the weighted series converges directly. In particular, mean-zero \(F\) satisfies the Gaussian Poincaré inequality \(\int F^2\,\mathrm d\gamma_d\le\int\lVert\nabla F\rVert^2\,\mathrm d\gamma_d\).

For \(0<\rho<1\), the Gaussian noise operator \[T_\rho Q(c)=\mathbb E_g Q(\rho c+\sqrt{1-\rho^2}\,g)\] multiplies \(\psi_I\) by \(\rho^{|I|}\), as follows by averaging its generating function. If \(Q\) is bounded and \(\sigma>0\), ordinary Gaussian convolution is smooth and \[ \partial_{c_x}\mathbb E_g Q(c+\sigma g) =\frac1\sigma\mathbb E_g g_xQ(c+\sigma g). \tag{3}\] Differentiation of the Gaussian density is justified by its integrable derivatives; an additional independent average may be included in \(Q\).

We also use the elementary sign identity underlying random-hyperplane rounding (Goemans and Williamson 1995, Lemma 3.2): if \(u,v\) are unit vectors and \(g\) is standard isotropic Gaussian, then \[ \mathbb P[\operatorname{sgn}\langle g,u\rangle\ne\operatorname{sgn}\langle g,v\rangle] =\frac{\angle(u,v)}\pi\le\lVert u-v\rVert. \tag{4}\] It follows by rotational symmetry in the two-dimensional plane spanned by \(u,v\); the collinear cases follow by continuity. In particular, adding an independent centered Gaussian of standard deviation \(a\) to a standard Gaussian changes its sign with probability \(\arctan(a)/\pi\le a\).

The starting gap and repetition

A finite two-player game consists of a joint distribution on questions \((U,V)\), finite answer sets, and an acceptance predicate. Its value is the maximum acceptance probability of separate deterministic response functions. Independent shared or private randomness does not increase this maximum: fixing the random seed realizes at least its average success. The ordinary \(r\)-fold repetition samples \(r\) independent question pairs and accepts only if all coordinates accept.

Folded proofs, face arrays, and queries

For a nonempty affine alphabet \(A\), a folded bit proof is a function \[f:\{P:A\to\{1,-1\}\}\longrightarrow\{1,-1\}, \qquad f(-P)=-f(P).\] A query is the Boolean function \(P\) itself: two descriptions that give the same function on \(A\) must receive the same answer. The intended proof at \(a\in A\) is evaluation, \(f(P)=P(a)\). The evaluation encoding is the long code of the label, and the displayed antisymmetry is the standard folding relation (Bellare et al. 1998; Håstad 2001). Nonemptiness of \(A\) ensures that \(P\ne-P\), so the folding requirement is consistent.

We allow a finite random index \(\xi\) with arbitrary probability weights to select an alphabet \(A_\xi\) and a folded proof \(f_\xi\). Conditional on \(\xi\), all sampling below is performed on its indicated alphabet. Expectations include \(\xi\) unless a conditioning is stated. Thus a bound on the average test failure will not be replaced by a bound for every individual index. We usually suppress \(\xi\) and write \(A,f\).

Let \(m,n\ge2\) be integers, to be selected later. Write \[X=[n]^m,\qquad N=n^m,\qquad \mathcal R=\{(i,y):i\in[m],\ y\in[n]^{[m]\setminus\{i\}}\}, \qquad M=|\mathcal R|=mn^{m-1}.\] Here \([n]^S\) denotes coordinate tuples indexed by \(S\). If \(x\in X\), then \(x_{-i}\) is the tuple obtained by deleting coordinate \(i\), and \(x_{-ij}\) deletes both \(i\) and \(j\). A row is one entry of an array \((B^i_y)_{(i,y)\in\mathcal R}\). We take these entries independently and uniformly from \(D(A)\) and put \[ B(x)=\sum_{i=1}^m B^i_{x_{-i}}\in D(A), \qquad B(a)=(B(x)(a))_{x\in X}. \tag{5}\] All sums of affine functions or binary arrays are over \(\mathbb F_2\). The face code is the subspace \[ \mathcal C=\left\{z\in\mathbb F_2^X: z_x=\sum_{i=1}^m z^i_{x_{-i}} \text{ for some }z^i\in\mathbb F_2^{[n]^{[m]\setminus\{i\}}}\right\}. \tag{6}\] In particular, \(B(a)\in\mathcal C\) for every \(a\in A\). The code depends only on \(m,n\), even when the index \(\xi\) changes the alphabet.

For \(u\in\mathbb R^X\) and \(d\in\mathbb R^{\mathcal C}\) define a table on \(\mathcal C\) by \[ P_{u,d}(z)=\operatorname{sgn}\left(\frac1{\sqrt N} \sum_{x\in X}u_x(-1)^{z_x}+d_z\right). \tag{7}\] Use a fixed convention at zero. Its pullback is the Boolean query \(P_{u,d}(B):a\mapsto P_{u,d}(B(a))\). If \(P\) is a table on \(\mathcal C\) and \(z\in\mathcal C\), write \(P^{z,+}\) and \(P^{z,-}\) for the same table with its entry at \(z\) forced to \(1\) and \(-1\), respectively. Repeated codewords among the labels present no difficulty: this operation changes the query value at every label with that codeword.

Let \(0<\eta\le\sigma<1\) and \(0<\delta<1\). Draw independent standard Gaussian vectors \(c,g\in\mathbb R^X\) and \(\lambda\in\mathbb R^{\mathcal C}\), independently of \(\xi,B\), and set \[P=P_{c+\sigma g,\eta\lambda}.\] The following tests fail precisely when the two indicated proof answers are unequal. A denominator is a positive weight normalization; it need not itself be a failure probability.

1. Compare \(f(P_{c,0}(B))\) and \(f(P(B))\), with denominator \(b_1=10\sigma\).

2. Independently for each row, replace \(B^i_y\) by a fresh uniform element of \(D(A)\) with probability \(\delta^2/m\), obtaining \(B'\). Compare \(f(P(B))\) and \(f(P(B'))\), using the same \(c,g,\lambda\) and the same table \(P\) on both sides. The denominator is \(b_2=10(\delta+\eta)\).

3. Draw \(z\) uniformly from \(\mathcal C\), independently of the other random choices, and compare \(f(P^{z,+}(B))\) and \(f(P^{z,-}(B))\). The denominator is \(b_3=|\mathcal C|^{-1}\).

Write \(\varepsilon_j\) for the failure probability of test (T\(j\)). Although the tables are defined at ties, every unforced threshold here has a continuous Gaussian input of positive variance, so the choice at ties does not affect any of these probabilities.

The decoding statement

For every folded proof define \[ F_B(c)=\mathbb E_{g,\lambda} f(P_{c+\sigma g,\eta\lambda}(B)), \qquad h_x(B,c)=\sqrt N\,\partial_{c_x}F_B(c). \tag{8}\] These derivatives exist everywhere by Gaussian convolution, as also verified below. For real arrays on \(X\) our conventions are \[\langle v,w\rangle_x=\frac1N\sum_{x\in X}v_xw_x, \qquad \lVert v\rVert_{2,x}^2=\frac1N\sum_{x\in X}|v_x|^2.\] If a row \((i,x_{-i})\) is removed, the remaining rows are its background. For any background write \(B[B^i_{x_{-i}}\leftarrow b]\) for the array with that row filled by \(b\in D(A)\).

The rest of this Section proves a low-degree correlation estimate. Section 4 turns that estimate into (9); the parameter choices in Section 4.6 complete the proof of Theorem 7.

Quantitative smoothing and degree projections

For the rest of this Section fix the following parameters, before choosing \(m,n\): \[ \sigma=\frac1{2560J},\qquad \delta=\eta=\frac{\sigma^2}{2560J},\qquad R=\lceil\delta^{-2}\rceil,\qquad T=\left\lceil\frac{32J}{\eta\sigma^4}\right\rceil. \tag{11}\] Choose an integer \(s\ge1\) such that \[ s+2>\sigma^{-2},\qquad (s+2)(1+\sigma^2)^{-(s+2)}\le\frac1{16}. \tag{12}\] Such an \(s\) is found by increasing integers and testing rational inequalities. The sequence \(k(1+\sigma^2)^{-k}\) tends to zero, and is decreasing once \(k>\sigma^{-2}\), since the ratio of its next term to its current term is \((1+1/k)/(1+\sigma^2)<1\). Thus these choices are effective and imply \[ \sup_{k\ge s+2} k(1+\sigma^2)^{-k}\le\frac1{16}. \tag{13}\] All constants in (11)–(12) are independent of the alphabet, its proof, and the integers \(m,n\).

The Fourier degree of a function of \(B\) is its degree in the independent rows. More precisely, a product character is \[\chi_{\boldsymbol\alpha}(B) =\prod_{(i,y)\in\mathcal R}(-1)^{\alpha^i_y(B^i_y)}, \qquad \alpha^i_y\in D(A)^*,\] and its degree is the number of nonzero \(\alpha^i_y\). This counts nonzero rows, regardless of the dimension of each row’s vector space. Gaussian degree means total degree \(|I|\) in the product Hermite basis \(\psi_I(c)\). Conditional on each \(\xi\), let \(\Pi_B\) project onto Fourier row degree at most \(Rm\), and let \(\Pi_c\) project onto Hermite degree at most \(s\). They act on different variables and commute. Define \[ L=\Pi_B\Pi_c h. \tag{14}\] The definition is coordinatewise in \(x\). Both projections also act orthogonally in the Hilbert space averaged over the arbitrary weights of \(\xi\).

Truth-table differentiation and a product-of-faces correlation

For a real array \(v\) on \(X\), define \[ \mathfrak d_X(v) =\max_{z\in\mathcal C}\left|\frac1N\sum_{x\in X}v_x(-1)^{z_x}\right| =\max_{z^1,\ldots,z^m} \left|\mathbb E_{x\in X}v_x\prod_{i=1}^m(-1)^{z^i_{x_{-i}}}\right|. \tag{21}\] The second maximum is over the binary face arrays appearing in (6); equality of the maxima follows from that definition. In particular \(\mathfrak d_X(v)\le\lVert v\rVert_{2,x}\).

At this stage \(m,n\) remain free. The next Section chooses \(m\) from \(R,s\), then a localization scale and \(n\), and finally \(p,\theta\). It uses (22) to prove the asserted one-row Fourier atom. In particular, the possibly large truth-table truncation constant \(T\) has been chosen before any of these later parameters.

Gauge identities and a partition selected by masks

We use two symmetries of \(h\) to find these equal, odd local frequencies. First fix distinct axes \(i,j\) and a tuple \(q\in[n]^{[m]\setminus\{i,j\}}\). For \(a\in D(A)\), add \(a\) to every row \(B^i_y\) with \(y_{-j}=q\) and every row \(B^j_y\) with \(y_{-i}=q\). Call the resulting array \(B^{(a)}\). At a point \(u\in X\), either both additions occur or neither occurs, so \(B^{(a)}(u)=B(u)\). Consequently \(h_x(B^{(a)},c)=h_x(B,c)\). Orthogonality, or a change of variables in the Fourier coefficient, shows that every nonzero coefficient satisfies \[ \sum_{y:y_{-j}=q}\alpha^i_y +\sum_{y:y_{-i}=q}\alpha^j_y=0 \qquad\text{in }D(A)^*. \tag{27}\] Indeed, otherwise some \(a\) makes the character change sign while the function remains unchanged.

For the second symmetry fix a row \(r=(i,v)\) and put \(k_u=\mathbf 1_{\{u_{-i}=v\}}\). This is a codeword in \(\mathcal C\). Let \(B+1_r\) denote addition of the constant-one affine function in this row, and let \(D_kc=((-1)^{k_u}c_u)_{u\in X}\). Translation of a codeword argument by \(k\) gives the exact identity \[P_{c+\sigma g,\eta\lambda}(z+k) =P_{D_kc+\sigma D_kg,\eta\lambda'}(z), \qquad \lambda'_z=\lambda_{z+k}.\] The Gaussian vectors \(D_kg\) and \(\lambda'\) have the original joint law. The proof is a function of the resulting Boolean table on \(A\), so \[F_{B+1_r}(c)=F_B(D_kc),\qquad h_x(B+1_r,c)=(-1)^{k_x}h_x(B,D_kc).\] The derivative in the second equality supplies its displayed sign. Since \(\psi_I(D_kc)=(-1)^{\sum_u k_u I_u}\psi_I(c)\), every nonzero coefficient also satisfies \[ \alpha_r(1)\equiv k_x+\sum_{u\in X}k_uI_u\pmod2. \tag{28}\] These identities hold separately for every proof index and for every alphabet.

Choose \(m>s+1\) so large that \[ \binom{m-s}{2}>Rm. \tag{29}\] Partition the terms of \(L_x\) as follows. Those with \(I_x>0\) form class \(0\). For each remaining pair \((I,S)\), choose two axes \(i<j\) subject to:

1. No \(u\) with \(I_u>0\) satisfies \(u_{-i}=x_{-i}\) or \(u_{-j}=x_{-j}\).

2. Among rows of \(S_i\) above \(x_{-ij}\), the only permitted row is \(x_{-i}\); among rows of \(S_j\) above \(x_{-ij}\), the only permitted row is \(x_{-j}\).

Such a pair exists. Since \(I_x=0\), each positive Hermite support point differs from \(x\). It can agree with \(x\) after deleting an axis for at most one axis, so at most \(s\) axes are forbidden by (i). A nonlocal row \(y\in S_i\), \(y\ne x_{-i}\), obstructs (ii) for at most one other axis \(j\): its coordinates must differ from \(x_{-i}\) only at \(j\). Thus all masks together forbid at most \(Rm\) unordered pairs. Inequality (29) leaves an admissible pair.

Fix an ordering of the pairs and choose the first admissible one. This rule uses only \(x,I,S\), never the values of the nonzero frequencies. Assign the entire exact-mask/Hermite component to that pair class. For a nonzero term in class \((i,j)\), apply (27) with \(q=x_{-ij}\). Condition (ii) leaves only the two local frequencies, so they are equal. Apply (28) to \(r=(i,x_{-i})\). Here \(k_x=1\) and condition (i) makes the Hermite sum zero. Therefore \[ \alpha^i_{x_{-i}}=\alpha^j_{x_{-j}}, \qquad \alpha^i_{x_{-i}}(1)=1. \tag{30}\] In particular both local rows really occur in the mask. Equality and oddness are consequences of the two symmetries, rather than extra conditions used to filter individual frequencies.

Write \(L^a\) for the class arrays, with \(a\in\mathcal K=\{0\}\cup\{(i,j):1\le i<j\le m\}\), and set \[ d_0=\frac{1}{4T(1+\binom m2)}. \tag{31}\] By subadditivity of \(\mathfrak d_X\) and Proposition 9, \[ \frac1{4T}\le\mathbb E\mathfrak d_X(L) \le\sum_{a\in\mathcal K}\mathbb E\mathfrak d_X(L^a). \tag{32}\] It will suffice to show, under failure of the asserted row-atom conclusion, that every summand is strictly less than \(d_0\).

Localization to a random subbox

Let \(2\le\ell<n\), with both integers to be chosen later. Independently on each axis choose a uniform \(\ell\)-element subset \(Y_i\subset[n]\), and put \(Y=\prod_iY_i\). The average of a uniform point in \(Y\), over this random choice, is uniform in \(X\). For every deterministic array \(v\), \[ \mathfrak d_X(v)\le\mathbb E_Y\mathfrak d_Y(v|_Y). \tag{33}\] To prove this, choose face signs attaining \(\mathfrak d_X(v)\), restrict them to \(Y\), and use that the original correlation is the average of their restricted correlations. The absolute value of the average is at most the average of the absolute values. This is a pointwise assertion and allows the maximizing face signs to depend on the full array.

For \(x\in Y\), retain from \(L^a_x\) only those terms whose positive Hermite support on \(Y\) is contained in \(\{x\}\) and whose masked rows on the faces of \(Y\) are contained in \(\{(r,x_{-r}):r\in[m]\}\). Denote the retained field by \(v^a_x\). Equivalently, \(v^a_x=Q^{a,Y}_xh_x\), where \(Q^{a,Y}_x\) is an orthogonal projection selecting complete exact-mask/Hermite components. In particular its choice depends only on \(a,Y,x,I,S\).

Conditional on a uniform point of \(Y\) being \(x\), the subsets \(Y_i\) are independent uniform \(\ell\)-subsets containing \(x_i\). For a fixed point \(u\ne x\), membership in \(Y\) requires that at least one particular value other than \(x_i\) be selected, so its conditional probability is at most \((\ell-1)/(n-1)\). The same assertion holds for a face tuple different from the corresponding face of \(x\). A term has at most \(s\) positive Hermite support positions and \(Rm\) masked rows. A union bound, followed by orthogonality for fixed \(x,Y\), therefore gives \[\begin{align*} \mathbb E\mathbb E_{x\in Y}|L^a_x-v^a_x|^2 &\le \sigma^{-2}(s+Rm)\frac{\ell}{n-1}, \tag{34}\\ \mathbb E\mathbb E_{x\in Y}|v^a_x|^2&\le\sigma^{-2}. \tag{35}\end{align*}\] For the first inequality one can sum the squared coefficients of \(L^a_x\) multiplied by their conditional removal probabilities; their total, averaged over uniform \(x\) and \(\xi\), is at most \(\sigma^{-2}\). For the second, each retained projection contracts the squared norm of \(h_x\), and then one averages over \(x,Y,\xi\). Thus the expected normalized \(L^1\) loss in localization is at most \[ e_{\mathrm{loc}}= \sigma^{-1}\sqrt{(s+Rm)\frac{\ell}{n-1}}. \tag{36}\] No pointwise bound on a retained field is needed here.

There are two useful conditional descriptions. For class \(0\), condition on \(\xi,Y\), all rows \(B\), and all Gaussians outside \(Y\). Each \(v^0_x\) is then a function of \(c_x\) alone, and its conditional mean is zero: every retained Hermite term has \(I_x>0\) and no other positive index on \(Y\).

For class \((i,j)\), condition on \(\xi,Y\), all Gaussians, all tables other than \(B^i,B^j\), and the rows of those two tables outside the faces of \(Y\). Call this background \(\mathcal F_{ij,Y}\). The remaining rows of these two tables are still independent and uniform. Localization and (30) give, for each \(x\in Y\), a function \(V_x:D(A)\to\mathbb R\), determined by this background, such that \[ v^{ij}_x=V_x(B^i_{x_{-i}}+B^j_{x_{-j}}), \qquad V_x(b)=\sum_{\alpha:\alpha(1)=1}\widehat V_x(\alpha)\chi_\alpha(b). \tag{37}\] Indeed, a retained term has no other on-subbox row in either table, and its two local character factors multiply to the character of their sum. Thus \(V_x\) is independent of the sampled values of every on-subbox row in tables \(i,j\). The slice norm \(\|V_x\|_2\) and its maximum Fourier coefficient are functions of \(\mathcal F_{ij,Y}\) as well. Integrating the two local rows makes their sum uniform, and hence (35) says \[ \mathbb E\mathbb E_{x\in Y}\|V_x\|_2^2\le\sigma^{-2}. \tag{38}\]

A coefficient estimate with no dependence on the alphabet

The next estimate connects the projected slices to the original field. For an axis \(i\) and point \(x\), put \(r=(i,x_{-i})\) and define the original maximum odd row coefficient by \[a_{x,i}(B_{\ne r},c)= \max_{\alpha:\alpha(1)=1} \left|\mathbb E_{b\in D(A)}h_x(B[r\leftarrow b],c)\chi_\alpha(b)\right|.\] This is a function only of the indicated background and the proof index. Its pointwise upper bound is \(\sqrt N/\sigma\).

Suppose, for a contradiction, that the row-atom conclusion in Theorem 7 fails for positive constants \(p,\theta\) to be chosen at the end. In this notation the failed assertion is \[\mathbb P_{\xi,x,i,B_{\ne(i,x_{-i})},c}[a_{x,i}\ge\theta]<p.\] Since \(i\) is uniform, for each fixed axis \(i\) this event has probability less than \(mp\). The pointwise bound on \(a_{x,i}\) gives \[ \mathbb E\mathbb E_{x\in X}a_{x,i}^2\le D, \qquad D=\theta^2+\frac{mpN}{\sigma^2}. \tag{40}\] This is only an averaged estimate in \(x,\xi\), which is exactly the estimate required in Lemma 10.

For a retained pair class use \(Q_x^Y=Q_x^{ij,Y}\) and the distinguished axis \(i\). From (37), its coefficient in the row \(B^i_{x_{-i}}\), when the other local row has value \(b'\), is \(\widehat V_x(\alpha)\chi_\alpha(b')\). The maximum magnitude is therefore precisely \(q_x=\max_{\alpha:\alpha(1)=1}|\widehat V_x(\alpha)|\), independently of \(b'\) or any other remaining row. Equations (39)–(40) imply \[ \mathbb E\mathbb E_{x\in Y}q_x\le C_0\sqrt D, \qquad \mathbb P[q_x>\gamma]\le\frac{C_0\sqrt D}{\gamma} \tag{41}\] for every \(\gamma>0\). The probability here is over a uniform point of \(Y\) and its slice background.

Bounded arrays and background-measurable slice operations

For \(A_0>0\), let \(\operatorname{clip}_{A_0}(z)= \max(-A_0,\min(z,A_0))\). We use \[ |z-\operatorname{clip}_{A_0}(z)|\le z^2/A_0. \tag{42}\]

For class \(0\), use its conditional description above and set \[w^0_x=\operatorname{clip}_{A_0}(v^0_x) -\mathbb E_{c_x}\operatorname{clip}_{A_0}(v^0_x).\] Here the conditional expectation fixes all rows and the Gaussians outside \(Y\). Since \(\mathbb E_{c_x}v^0_x=0\), inequality (42) bounds both the clipping loss and the absolute value of the subtracted mean. Thus \[ |w^0_x|\le2A_0,\qquad \mathbb E\mathbb E_{x\in Y}|v^0_x-w^0_x|\le\frac{2\sigma^{-2}}{A_0}. \tag{43}\] Conditioned on that common background, the variables \(w^0_x\), \(x\in Y\), depend on distinct independent Gaussians and have mean zero.

For class \((i,j)\), operate on the entire slice \(V_x\) as follows:

1. Set the slice to zero if \(\|V_x\|_2>H\).

2. Set it to zero if \(q_x>\gamma\).

3. Clip every value of a remaining slice to \([-A_0,A_0]\).

Both discard decisions depend only on \(\mathcal F_{ij,Y}\). In particular, a decision is made from the function of the free sum variable and is independent of the sampled local rows. Let \(W_x\) be the resulting slice and \(w^{ij}_x=W_x(B^i_{x_{-i}}+B^j_{x_{-j}})\).

Write \(\nu_x=\|V_x\|_2\). The first discard costs at most \[\mathbb E\mathbb E_{x\in Y}\nu_x\mathbf 1_{\{\nu_x>H\}} \le H^{-1}\mathbb E\mathbb E_{x\in Y}\nu_x^2\le\frac{\sigma^{-2}}H.\] For the second discard, Cauchy–Schwarz, (38) and (41) give the bound \[ e_{\mathrm{atom}}= \sigma^{-1}\sqrt{C_0/\gamma}\,D^{1/4}. \tag{44}\] Indeed its loss is at most \(\mathbb E\mathbb E_{x\in Y}\nu_x\mathbf 1_{\{q_x>\gamma\}}\), regardless of whether the first discard has already occurred. The last clipping operation costs at most \(\sigma^{-2}/A_0\) by (42). Consequently \[ \mathbb E\mathbb E_{x\in Y}|v^{ij}_x-w^{ij}_x| \le\frac{\sigma^{-2}}H+e_{\mathrm{atom}}+ \frac{\sigma^{-2}}{A_0}. \tag{45}\]

Every processed slice has absolute bound \(A_0\) and \(L^2\) norm at most \(H\). For a slice surviving both discards, its clipping error in conditional \(L^1(D(A))\) is at most \(H^2/A_0\). Each Fourier coefficient changes by at most this amount. Before clipping the spectrum was odd and all its coefficients had magnitude at most \(\gamma\), so, for all frequencies, \[ \|W_x\|_2\le H,\qquad \max_\alpha|\widehat W_x(\alpha)|\le\varepsilon_0, \qquad \varepsilon_0=\gamma+H^2/A_0. \tag{46}\] Discarded slices satisfy the same bounds. Symmetric clipping in fact preserves oddness, since \(V_x(b+1)=-V_x(b)\), although the following estimate only needs the bound for all coefficients.

Box Cauchy–Schwarz and the independent squares

We prove the deterministic inequality used to remove the face signs. This is the iterated Cauchy–Schwarz mechanism of the box norms in hypergraph-uniformity arguments (Gowers 2007, sec. 3.5 and Lemma 4.1). The conditional square calculation that follows is specific to our localized array. For a finite product \(Y=\prod_{j=1}^mY_j\) and an array \(v:Y\to\mathbb R\), let \(u^0,u^1\) be independent uniform points of \(Y\) and set \(u^\omega=(u_1^{\omega_1},\ldots,u_m^{\omega_m})\) for \(\omega\in\{0,1\}^m\).

Apply Lemma 11 pointwise to a processed random field \(w\), before averaging any of its randomness. Write \(Q=2^m\). By Jensen’s inequality, \[ (\mathbb E\mathfrak d_Y(w))^Q \le\mathbb E\mathfrak d_Y(w)^Q \le\mathbb E\mathbb E_{u^0,u^1}\prod_\omega w(u^\omega). \tag{48}\] The choices with \(u_i^0=u_i^1\) for at least one \(i\) have probability at most \(m/\ell\). Since all processed fields have bound \(2A_0\), their contribution to the last expectation is at most \((m/\ell)(2A_0)^Q\) in absolute value.

On a cube with no repeated coordinates, all its vertices are distinct. For class \(0\), condition on all rows and on the Gaussians outside \(Y\). The factors \(w^0(u^\omega)\) are independent centered functions of distinct \(c_{u^\omega}\), so their product has conditional mean zero. Thus \[ \mathbb E\mathfrak d_Y(w^0)\le 2A_0(m/\ell)^{1/2^m}. \tag{49}\]

For class \((i,j)\), condition instead on \(\mathcal F_{ij,Y}\) and on the chosen cube without repetitions. Partition its vertices into \(2^{m-2}\) squares by fixing all coordinates other than \(i,j\). On any one square its four local sums have the form \[r_a+s_b,\qquad (a,b)\in\{0,1\}^2,\] where \(r_0,r_1\) are the two rows of table \(B^j\), and \(s_0,s_1\) the two rows of table \(B^i\). These four rows are independent and uniform in \(D(A)\). Figure 1 displays the shared rows. The four sums are uniform subject to their zero-sum relation; they are not four independent variables.

For four possibly different real slice functions \(W_{ab}\), direct Fourier expansion gives \[ \mathbb E_{r_0,r_1,s_0,s_1} \prod_{a,b\in\{0,1\}}W_{ab}(r_a+s_b) =\sum_\alpha\prod_{a,b\in\{0,1\}}\widehat W_{ab}(\alpha). \tag{50}\] Indeed averaging \(r_0,r_1\) forces the two frequencies in each row of the square to agree, and averaging \(s_0,s_1\) forces agreement between these rows. Using the coefficient bound on two factors and Cauchy–Schwarz and Parseval on the other two, the absolute value of (50) is at most \[ \varepsilon_0^2\sum_\alpha |\widehat W_{10}(\alpha)\widehat W_{11}(\alpha)| \le\varepsilon_0^2H^2. \tag{51}\]

Different squares use disjoint rows in both tables: any change in one of the other \(m-2\) coordinates changes a retained coordinate of every such row. Conditional on the fixed background, their products are consequently independent. Their slice functions may share that background, which does not affect this independence. The absolute conditional expectation of the full cube product is therefore at most \((\varepsilon_0^2H^2)^{2^{m-2}}\). Combining this with the collision bound and (48), and using \((a+b)^{1/Q}\le a^{1/Q}+b^{1/Q}\) for \(a,b\ge0\), gives \[ \mathbb E\mathfrak d_Y(w^{ij}) \le2A_0(m/\ell)^{1/2^m} +\sqrt{H(\gamma+H^2/A_0)}. \tag{52}\] The maximizing face signs were eliminated by the deterministic inequality before the conditional independence argument was used. No independence assumption about those signs is involved.

Choosing parameters and completing inner decoding

For any two fields on a fixed box, \(|\mathfrak d_Y(u)-\mathfrak d_Y(v)|\le\mathbb E_{x\in Y}|u_x-v_x|\). Thus (33), localization, the processing losses, and (52) imply, for each pair class, \[\begin{align*} \mathbb E\mathfrak d_X(L^{ij}) \le{}&\underbrace{\sigma^{-1} \sqrt{(s+Rm)\ell/(n-1)}}_{e_{\mathrm{loc}}} +\frac{\sigma^{-2}}H +\underbrace{\sigma^{-1}\sqrt{C_0/\gamma} (\theta^2+mpN/\sigma^2)^{1/4}}_{e_{\mathrm{atom}}} \\ &+\frac{\sigma^{-2}}{A_0} +2A_0(m/\ell)^{1/2^m} +\sqrt{H(\gamma+H^2/A_0)}. \tag{53}\end{align*}\] For class \(0\), the corresponding bound is \[ \mathbb E\mathfrak d_X(L^0) \le e_{\mathrm{loc}}+\frac{2\sigma^{-2}}{A_0} +2A_0(m/\ell)^{1/2^m}. \tag{54}\]

Questions, fresh slots, and canonical functions

For an equation \(E\), put \[A(E)=\{a\in\mathbb F_2^3: a_1+a_2+a_3=\tau_E,\quad a_p=a_{p'}\text{ whenever }v(E,p)=v(E,p')\}.\] This is a nonempty affine space of dimension at most two. Indeed, after identifying repeated variable names, there are \(k\le3\) free bit slots and one nonzero linear equation: at least one multiplicity is odd because the sum of the multiplicities is three. The equation therefore has rank one, and \(\dim A(E)=k-1\).

Fix integers \(t\ge t_0\ge1\). An outer sample \(e\) is drawn as follows. First draw \(t\) independent uniform list entries, with resulting equation questions \(E_1,\ldots,E_t\), and let \[U=(E_1,\ldots,E_t),\qquad A_U=\prod_{j=1}^t A(E_j).\] Next draw a uniform \(t_0\)-element subset \(H\subseteq[t]\). For each \(j\in H\), independently draw \(p_j\in[3]\) uniformly. The second question is the ordered, tagged tuple \(V=(V_1,\ldots,V_t)\), where \[V_j=\begin{cases} (\mathrm{variable},v(E_j,p_j)),&j\in H,\\ (\mathrm{equation},E_j),&j\notin H. \end{cases}\] In particular, a variable question contains its variable name and the coordinate \(j\) in the ordered tuple, but neither its position \(p_j\) nor its originating equation. Set \[A_V=\prod_{j=1}^t A_{V,j},\qquad A_{V,j}=\begin{cases}\mathbb F_2,&j\in H,\\\mathbb F_2^3,&j\notin H.\end{cases}\] Every displayed slot in this product is unrestricted. Even when the same variable name occurs more than once, no equalities between these slots are imposed. Likewise, the slots belonging to distinct coordinates of \(A_U\) are separate; its only equalities between repeated names are those inside a single factor \(A(E_j)\). These fresh slots are essential both to independent repetition and to the distribution of affine forms below.

Define the affine map \(\pi_e:A_U\to A_V\) coordinatewise by \[ (\pi_e(a))_j=\begin{cases}(a_j)_{p_j},&j\in H,\\a_j,&j\notin H.\end{cases} \tag{55}\] The verifier accepts labels \(a\in A_U\) and \(b\in A_V\) precisely when \(\pi_e(a)=b\). The map need not be onto: the unrestricted full triples on the second side need not satisfy their equations. Pullback is the linear map \[\pi_e^*:D(A_V)\longrightarrow D(A_U),\qquad L\longmapsto L\circ\pi_e,\] and preserves the constant-one function.

We specify exactly what a question and an affine hint reveal. Every actual \(U\) or \(V\) is the tuple just defined, without extra information identifying its occurrence in \(e\). Put its alphabet in lexicographic order as a subset of its displayed bit slots. A function on that alphabet is represented by its complete truth table in this order. In particular, a hint in \(D(A_U)\) or \(D(A_V)\) is the function itself, with this canonical encoding. It is not accompanied by a formula, its original coefficients on another alphabet, or an encoding of the map through which it was pulled back. Equal functions on the same actual question have equal encodings. The same convention will apply to Boolean queries in the bit proofs. Thus a response function at a given question cannot distinguish different descriptions of the same query.

For an integer \(q\ge0\), the game with \(q\) affine hints additionally draws independent uniform functions \(L_1,\ldots,L_q\in D(A_V)\). The first player receives \[(U,\pi_e^*L_1,\ldots,\pi_e^*L_q)\] and the second receives \((V,L_1,\ldots,L_q)\). The acceptance condition is still \(\pi_e(a)=b\). Giving independent shared or private randomness to these players does not change the upper bounds on its value.

Soundness despite the affine hints

Consider first the ordinary equation-versus-variable game: draw a uniform list entry \(E\), choose a uniform position \(p\in[3]\), give \(E\) to the first player and only \(v(E,p)\) to the second, and ask for \(a\in A(E)\) and a bit \(b\). Accept when \(a_p=b\). Equivalently the first answer alphabet can be \(\mathbb F_2^3\) with invalid answers rejected, so the answer sizes are at most eight and two.

Joint marginal smoothness

The following estimate concerns the joint distribution of several forms pulled back through the same outer sample. Conditioning is on \(U\) only; in particular it is not conditioning on any previously received hint. For finite probability distributions \(\mu,\nu\), use \(\operatorname{TV}(\mu,\nu)=\frac12\sum_x\lvert\mu(x)-\nu(x)\rvert\).

Finally, these outer games are explicit finite objects. Their complete sampling space has \[M_0^t\binom{t}{t_0}3^{t_0}\] equally likely draws, counting repeated list entries with their multiplicities. There are at most \(2^{2t}\) labels at a first question and \(2^{3t-2t_0}\) labels at a second question. Their affine spaces, functions, canonical truth tables, and projections are all enumerable by binary linear algebra and finite evaluation. For fixed \(t,t_0,q,d\) these local enumerations have constant size independent of the input. Comparing actual question encodings and identifying equal ones takes polynomial bit complexity. Thus the fresh-slot and canonical-function conventions introduce no oracle or uncharged lookup table.

Rational Gaussian sign tables

Let \(c,g\in\mathbb R^X\) and \(\lambda\in\mathbb R^{\mathcal C}\) have independent standard Gaussian coordinates. Define the two tables on \(\mathcal C\) \[\begin{align*} T_0(z)&=\operatorname{sgn}\left(N^{-1/2}\sum_{x\in X}c_x(-1)^{z_x}\right),\\ T_1(z)&=\operatorname{sgn}\left(N^{-1/2}\sum_{x\in X}(c_x+\sigma g_x)(-1)^{z_x} +\eta\lambda_z\right). \end{align*}\] Their pair is a random element of a finite set of size \(2^{2|\mathcal C|}\). All four tests are deterministic functions of this pair and their finite random choices. The first uses both tables. The second uses the same \(T_1\) for \(B\) and \(B'\). The third forces one entry of \(T_1\) to the two specified values. The fourth uses the same \(T_1\) on the two outer alphabets. Thus a single approximation of \((T_0,T_1)\) suffices.

Numerical multiplicities and canonical proof variables

Let \(M_0\ge1\) be the length of the uniform equation list from Theorem 4. The rounding needed to obtain that list was included in its proof. Set \[H_K=\binom{t}{t_0}3^{t_0},\qquad M=mn^{m-1}.\] There are exactly \(H_KM_0^t\) elementary outer samples: ordered choices of list entries, a hidden-coordinate set, and a position at every hidden coordinate. Each has probability \(1/(H_KM_0^t)\). For the first three tests enumerate the full outer sample and ignore its unused information; this gives exactly the required second-question marginal. Repeated question encodings are identified as specified in Section 5. The sampling indices are not appended to actual questions.

All remaining probability denominators divide an effectively computable integer \(A_K\) depending only on \(K\). An explicit choice can be given. Write the row-resampling probability in lowest terms as \(\delta^2/m=a_0/r_0\), and use the Gaussian-table denominator \(Q\) from Lemma 17. Each second alphabet has dimension at most \(3t\), so a uniform row in \(D(A_V)\) has a probability denominator dividing \(2^{3t+1}\). Sample both the original and fresh replacement arrays even when some or all replacement rows are unused, and similarly allow the unused resampling flags and forced codeword to be drawn in every test. Their joint probabilities have denominators dividing \[ A_K=Q\,2^{2M(3t+1)}r_0^M|\mathcal C|. \tag{75}\] Every elementary test outcome therefore has probability \(a/(H_K A_K M_0^t)\) for a nonnegative integer \(a\). Dummy choices do not change any test’s distribution. They only give a uniform denominator.

Write \(b_j=s_j/t_j\) in lowest terms, with positive integers \(s_j,t_j\), and choose a positive integer \(B_K\) divisible by all four \(s_j\). The common denominator for the cost weights can now be taken to be \[ D_0=C_KM_0^t,\qquad C_K=H_KA_KB_K. \tag{76}\] Indeed an elementary outcome of test \(j\) contributes weight \(a t_j/(H_KA_KM_0^t s_j)\) times its failure indicator, and multiplication by \(D_0\) gives the integer \(aB_Kt_j/s_j\). Zero multiplicities may be omitted. Summing all multiplicities, before or after collecting equal demands, gives exactly \[ \sum_{\text{elementary demands}}\text{multiplicity} =D_0\sum_{j=1}^4b_j^{-1}=D_0W=O_K(M_0^t). \tag{77}\] This is a bound on their numerical sum, so expanding the multiplicities is polynomial work for fixed \(K\).

We describe explicitly the finite proof variables to which these demands refer. Each \(A_U\) is a nonempty affine subset of at most \(3t\) bit slots, and each \(A_V\) has at most \(3t\) slots. List each alphabet in lexicographic order. Its affine forms can be found by binary Gaussian elimination and enumerated by their truth tables; there are at most \(2^{3t+1}\) forms. Its Boolean query tables can all be enumerated as well, in number at most \(2^{2^{3t}}\). These are constants for fixed \(K\). All pullbacks and the arrays \(B(x)\) are evaluated on these explicit tables. In particular, the construction never computes a smoothed derivative, a Fourier decoder, or an optimum proof.

For each actual question on each side, introduce one sign variable for every complementary pair \(\{P,-P\}\) of Boolean tables on its alphabet. The two tables are distinct because the alphabet is nonempty. If \(a_*\) is its first label, define \[\tau(P)=P(a_*),\qquad R(P)=\tau(P)P.\] The representative \(R(P)\) takes value \(+1\) at \(a_*\). Assigning a sign \(y_{q,R}\in\{-1,1\}\) to each such representative is in bijection with folded proofs, by \[ f_q(P)=\tau(P)y_{q,R(P)}. \tag{78}\] Here \(q\) includes the first- or second-side tag and the actual question, but no description of an outer-sample occurrence. Identical semantic query tables at the same question therefore use the same variable.

A comparison \(f_q(P)=f_{q'}(P')\) becomes the signed demand \[ y_{q,R(P)}y_{q',R(P')}=\tau(P)\tau(P'). \tag{79}\] The required relation is equality when the right side is \(+1\) and inequality when it is \(-1\). This formula applies even when the two variables coincide: a self-equality never fails and a self-inequality always fails. Equation (78) proves exact equality between weighted demand cost and \(\operatorname{Cost}_{\mathrm{fin}}\), for every assignment, including these cases.

Exact realization by an unweighted simple graph

The strict gap and algorithmic consequences

For clarity, the deterministic and randomized approximation consequences are distinct. Let \(C>1\) be a fixed real factor and choose a fixed integer \(K\ge\max\{2,C\}\). A deterministic polynomial-time algorithm returning a bipartition of cost at most \(C\operatorname{OPT}_{\mathrm{uncut}}(G)\) would decide \(3\)SAT: run it on the output graph and accept exactly when its cut has cost at most \(Kk\). In a YES instance its cost is at most \(Ck\le Kk\); in a NO instance every bipartition costs more than \(Kk\). Thus such an algorithm implies \(\mathsf P=\mathsf{NP}\).

If instead a randomized polynomial-time algorithm returns such a bipartition with probability at least a fixed positive constant, validate the returned bipartition and apply the same cost check. A NO instance can never be accepted, regardless of the algorithm’s random choices. A YES instance is accepted whenever the approximation succeeds. Independent repetition a fixed number of times raises this probability to at least \(1/2\) if necessary. This puts \(3\)SAT in \(\mathsf{RP}\), and composing with deterministic reductions to \(3\)SAT gives \(\mathsf{NP}\subseteq\mathsf{RP}\). The randomized conclusion is therefore the latter containment.

Minimum 2CNF clause deletion