1 Introduction
For a finite simple undirected graph G=(V,E) and a bipartition V=S\sqcup(V\setminus S), define
The two parts may be empty and need not be balanced. Equivalently, \OPT_{\rm uncut}(G) is the minimum number of edges whose deletion makes G bipartite: deleting the uncut edges of a partition suffices, and a bipartition of any remaining bipartite graph makes every uncut edge belong to the deleted set. This is the edge-deletion problem throughout.
Min-UnCut measures distance from bipartiteness. Although its objective is the number of edges minus the maximum cut size, a multiplicative approximation for Max-Cut does not give a comparable multiplicative approximation for Min-UnCut when the graph is nearly bipartite. Its approximation question therefore concerns how accurately one can recognize and exploit that regime. Agarwal, Charikar, Makarychev and Makarychev gave a randomized polynomial-time O(\sqrt{\log |V|}) approximation for Min-UnCut [1, Theorem 2.1]. Under the Unique Games Conjecture, the near-satisfiable Max-Cut gap of Khot, Kindler, Mossel and O’Donnell implies arbitrarily large constant gaps for weighted Min-UnCut [9]: graphs admitting a cut that misses at most an \eta fraction of the total edge weight are hard to distinguish from graphs in which every cut misses a constant times \sqrt\eta of that weight. The ratio of these two uncut costs grows without bound as \eta decreases.
Unconditional lower bounds for particular constants have developed through successively stronger finite gadgets. Håstad, Huang, Manokaran, O’Donnell and Wright proved hardness for every factor below 11/8 in the weighted minimum-deletion formulation of Max-Cut [7, Corollary 3.3]. Wiman strengthened the near-satisfiable Max-Cut gap to give factors below 1.45685 [15, Theorem 3.18]. Martinsson subsequently obtained hardness for every factor below 73139148/49096883\approx1.48969 for minimizing the weight of violated two-variable parity equations [12, Theorem 1.1]. The last result transfers to weighted Min-UnCut by replacing equality and inequality constraints by paths of lengths four and three, respectively, with fresh internal vertices and the constraint’s weight on each edge. For fixed endpoint bits each path has minimum uncut weight equal to the violated constraint’s weight, so this preserves absolute minimum cost even though the total weight changes. These results concern individual constant factors; the theorem below gives every prescribed constant factor on simple unweighted graphs.
Theorem 1.1. For every fixed integer K\ge2, there is a deterministic polynomial-time many-one reduction mapping a 3SAT formula \varphi to a pair (G,k), where G is an explicit finite simple undirected unweighted graph and k\ge1 is a binary-encoded integer, such that
For each fixed K, the graph size, full construction work, and bit complexity are polynomial in the bit length of \varphi. All constants are effective; no advice or oracle is supplied to the reduction.
Theorem 1.1 resolves the constant-factor approximability question for Min-UnCut in the hardness direction. It assumes neither the Unique Games Conjecture nor any other unproved hardness hypothesis. Choosing an integer K at least any prescribed real factor C>1 shows that a deterministic polynomial-time C-approximation would imply \mathsf P=\NP. The positive threshold k separates this assertion from ordinary bipartiteness testing. For a randomized approximation with constant success probability, the corresponding consequence is \NP\subseteq\RP; Section 7 explains the one-sided test.
In minimum 2CNF clause deletion, the input is an explicit list of two-literal disjunctions, each of unit cost, and one deletes as few clause occurrences as possible to make the remaining formula satisfiable. Write \OPT_{\rm del}(F) for this minimum and \operatorname{unsat}(F,a) for the number of clause occurrences falsified by an assignment a. Agarwal et al. also give a randomized polynomial-time O(\sqrt{\log n}) approximation for this problem on n variables [1, Theorem 3.1].
Corollary 1.2. For every fixed real C>1, minimum 2CNF clause deletion is NP-hard to approximate within factor C. In particular, a deterministic polynomial-time C-approximation would imply \mathsf P=\NP.
The proof in Section 7.5 replaces each edge by two clauses and preserves the optimum deletion cost exactly.
1.1 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.
A game with affine labels. The starting point is Håstad’s near-satisfiable gap for three-variable parity equations [6], recalled with ordinary parallel repetition in Section 2. A first player receives a tuple of equations and labels it by satisfying assignments to the separate equations. A second player sees the full equations in most coordinates and only a queried variable in a small set of hidden coordinates. Its label supplies the corresponding bits. The verifier checks agreement. The two label sets are finite affine spaces over \F_2, and agreement is an affine map from the first space to the second.
Section 5 proves two properties of this game. Its soundness survives giving both players a fixed number of shared affine functions on their labels: many hidden coordinates have zero coefficients in all those functions and still support ordinary repetition. Also, a fixed number of uniform affine functions on the second alphabet, pulled back through the random agreement map, have joint distribution close to independent uniform functions on the first alphabet. The latter is a statement about the whole collection; it allows later decoding choices to depend on some of its members. These properties are proved directly for the questions used here.
A comparison test for arbitrary bit proofs. At each question with alphabet A, replace a label a by a function f assigning a sign f(P)\in\{1,-1\} to every Boolean query P:A\to\{1,-1\}. The intended function evaluates queries, f(P)=P(a). Arbitrary functions are required only to satisfy f(-P)=-f(P), the usual folding relation. We must extract labels from arbitrary such functions whose comparison cost is small.
Section 3 constructs three tests using random affine functions and Gaussian thresholds. The affine functions are arranged on X=[n]^m as sums of m arrays, with the ith array independent of the ith coordinate. Each test compares two queries obtained by a controlled change of this data. The tests respectively control Gaussian perturbations, resampling of array entries, and changes in individual entries of a Boolean truth table. Evaluation proofs have small cost in all three tests.
For a general proof, Gaussian averaging gives a smooth real-valued function of the threshold parameters. Its gradient retains nonzero energy because the first test rarely changes the answer. The other two tests control its Fourier degrees and its correlation with products of functions each missing one coordinate of X. These bounds use the number of array positions, not the number of affine labels.
Extracting a label without an alphabet-size loss. Section 4 converts that correlation into a large Fourier coefficient in one affine-function entry, with all other entries fixed. The coefficient is odd: its character changes sign upon adding the constant function 1. Each such character has the form b\mapsto(-1)^{b(a)} for a unique label a, by Lemma 2.1.
The extraction uses symmetries of the array representation to pair equal odd frequencies. Restricting to a random smaller box then separates their remaining random variables. Repeated Cauchy–Schwarz removes the arbitrary functions missing coordinates and leaves products over cube vertices. The terms involving the Gaussian coordinate at the tested point vanish by centering, while the paired terms factor over independent four-corner squares, each controlled by a Fourier coefficient. The selection of terms depends only on which array entries and Gaussian degrees occur; it never enumerates label frequencies. This distinction gives an extraction probability and coefficient size independent of the affine alphabet.
Composition and finite graphs. Section 6 adds a fourth test comparing the two players’ answers to the same pulled-back query. Low cost makes their smoothed one-entry functions close. The large coefficients on each side form short label lists. Joint approximation of the affine-function distributions controls the remaining small coefficients through a fourth-moment identity, even when the first list was chosen using shared background functions. The lists yield an agreeing pair with fixed positive probability, contradicting the game’s soundness. All inner constants are fixed before the game’s repetition parameters and alphabet.
Finally, Section 7 approximates the complete joint Gaussian sign tables by a rational law. Enumerating this law gives a deterministic comparison system with polynomial numerical multiplicities for fixed K. Fresh paths of lengths four and three realize equality and inequality demands exactly, including demands with coincident endpoints. Their costs have no additive baseline, so a positive integer threshold preserves the strict multiplicative gap. The constants may be large; the approximation factor is fixed before the input formula is given.
1.2 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 [6, 14, 8]. 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 [2], 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 [11, Sections 3.2–3.4 and 5.2]. Shared linear advice and coordinates on which that advice vanishes appear in Khot, Minzer and Safra [10, Sections 3.3–3.4]; a related shared-subspace formulation appears in Dinur et al. [3, 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 [4], and Gaussian smoothing and Hermite expansions are standard in noise-stability analysis [13]. The box estimate uses the iterated Cauchy–Schwarz mechanism in Gowers’s hypergraph arguments [5]. 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.
2 Preliminaries and unconditional starting theorems
All finite-set averages and Fourier transforms use probability normalization. Every affine space in the paper is a finite nonempty affine space over \F_2. Constants described as fixed are independent of the input instance; their dependence on the requested approximation factor is allowed.
2.1 Affine alphabets and odd characters
For an affine space A, let D(A) be the vector space of affine functions A\to\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.
Lemma 2.1 (Odd frequencies are labels). The map a\mapsto\operatorname{ev}_a, where \operatorname{ev}_a(b)=b(a), is a bijection from A onto the odd frequencies of D(A). If \pi:A\to A' is affine and \pi^*:D(A')\to D(A) is pullback, then its dual sends \operatorname{ev}_a to \operatorname{ev}_{\pi(a)}.
Proof. Choose affine coordinates A=\F_2^r. Every affine function is b(x)=b_0+\sum_{j=1}^r b_jx_j. A functional taking the constant function to one is uniquely b\mapsto b_0+\sum_j b_ja_j, for some a\in\F_2^r. Finally (\pi^*)^*(\operatorname{ev}_a)(b)=b(\pi(a)).
For a real function v on a finite binary vector space W, write
Character orthogonality gives Parseval’s identity \sum_\alpha\abs{\widehat v(\alpha)}^2=\E v^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
Indeed, expansion of the four factors and averaging over the three independent points force all four frequencies to agree.
2.2 Gaussian identities
We recall the Fourier–Hermite identities used in Gaussian noise-stability analysis [13, Sections 4.1 and 5], with proofs of the needed forms. Let \gamma_d be standard Gaussian probability measure on \R^d. The normalized Hermite polynomials H_j are specified by
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,
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\dd\gamma_d\le\int\norm{\nabla F}^2\dd\gamma_d.
For 0<\rho<1, the Gaussian noise operator
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
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 [4, Lemma 3.2]: if u,v are unit vectors and g is standard isotropic Gaussian, then
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.
2.3 The starting gap and repetition
Theorem 2.2 (An unconditional equation gap). For every fixed rational \zeta>0, there is a deterministic polynomial-time reduction from 3SAT to a nonempty explicit list of equations x_i+x_j+x_k=b over \F_2, with uniform sampling from the list, such that satisfiable inputs admit an assignment satisfying at least 1-\zeta of the list and unsatisfiable inputs admit none satisfying more than 3/4. The list length and the full bit complexity are polynomial for fixed \zeta.
Proof. Håstad’s Theorem 5.4, including the verifier-to-equations construction in its proof, gives a deterministic polynomial construction of rationally weighted three-variable equations with YES value at least 1-\delta and NO value at most (1+\delta)/2, for every fixed sufficiently small dyadic \delta>0 [6]. Here the weights and their polynomial-size support are explicit.
We record why a uniform list costs only polynomial work. For a probability vector (w_1,\ldots,w_r) of rational weights and an integer Q, take \lfloor Qw_j\rfloor copies of equation j and distribute the remaining copies among the largest fractional remainders. The resulting probabilities differ from the original ones in total variation by at most r/(2Q). All floors, comparisons and sorting require polynomial bit complexity. Choose a fixed \eps>0 and \delta>0 with \delta+\eps<\zeta and (1+\delta)/2+\eps<3/4, then Q\ge r/(2\eps) with Q=O_\eps(r). Satisfaction probabilities change by at most \eps for every assignment simultaneously, giving the asserted list. The underlying construction can be taken nonempty; any exceptional bounded input cases are decidable directly and replaced by fixed YES or NO lists.
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.
Theorem 2.3 (Uniform parallel repetition). There is an effectively specified constant c<1 such that every finite game with at most eight first-player answers, at most two second-player answers, and value at most 11/12 has r-fold repeated value at most c^r for all integers r\ge0. The same c works for all question distributions and all question-set sizes.
Proof. This is an instance of ordinary parallel repetition [14]. More explicitly, Theorem 2.5 of Holenstein [8], after padding the answer sets to sizes eight and two, permits
Holenstein’s Theorem 2.5 imposes no regularity condition on the joint question distribution. A rational upper bound strictly between this c and one may be used in every effective parameter choice below.
3 The bit test and its smoothed correlation
We first define the inner test, including the distribution of its queries. Its soundness statement is uniform in the size of the affine alphabet. This uniformity will permit us to select the inner parameters before the outer repetition parameters.
3.1 Folded proofs, face arrays, and queries
For a nonempty affine alphabet A, a folded bit proof is a function
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 [2, 6]. 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
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
All sums of affine functions or binary arrays are over \F_2. The face code is the subspace
In particular, B(a)\in\C for every a\in A. The code depends only on m,n, even when the index \xi changes the alphabet.
For u\in\R^X and d\in\R^{\C} define a table on \C by
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 \C and z\in\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\R^X and \lambda\in\R^{\C}, independently of \xi,B, and set
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.
- (T1)
Compare f(P_{c,0}(B)) and f(P(B)), with denominator b_1=10\sigma.
- (T2)
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).
- (T3)
Draw z uniformly from \C, independently of the other random choices, and compare f(P^{z,+}(B)) and f(P^{z,-}(B)). The denominator is b_3=|\C|^{-1}.
Write \eps_j for the failure probability of test (Tj). 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.
Lemma 3.1 (Honest proof budgets). For any choice of labels a_\xi\in A_\xi, the evaluation proofs f_\xi(P)=P(a_\xi) satisfy \eps_j\le b_j for j=1,2,3. In fact,
Proof. Condition on the index and its label a. For any z\in\C, put
For the first test, conditional on B, the input \ip{c}{v_{B(a)}} is standard Gaussian, and its added perturbation \sigma\ip{g}{v_{B(a)}}+\eta\lambda_{B(a)} is an independent Gaussian of standard deviation \sqrt{\sigma^2+\eta^2}. The sign identity (2.4) gives disagreement probability
For the second test, let D be the relative Hamming distance between B(a) and B'(a). For each x, the evaluation B(x)(a) can change only if at least one of its m rows was selected for resampling. A union bound therefore gives \E D\le\delta^2. Consequently
Conditional on B,B', apply (2.4) to the isotropic Gaussian c+\sigma g, initially omitting the table perturbations. Its two signs disagree with probability at most \norm{v_{B(a)}-v_{B'(a)}}. Restoring each perturbation \eta\lambda_{B(a)} or \eta\lambda_{B'(a)} changes the corresponding sign with probability at most \eta/\sqrt{1+\sigma^2}\le\eta. The union bound gives \eps_2\le2\delta+2\eta. Independence of the two table perturbations is not needed, so this reasoning also covers B(a)=B'(a).
In the third test, the two evaluation answers differ if and only if z=B(a). Uniform sampling of z gives exactly |\C|^{-1}. All bounds hold conditional on the chosen label and can be averaged over \xi.
3.2 The decoding statement
For every folded proof define
These derivatives exist everywhere by Gaussian convolution, as also verified below. For real arrays on X our conventions are
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).
Theorem 3.2 (Inner decoding). For every rational J\ge1, there are effectively selectable integers m,n\ge2 and positive rational constants \sigma,\delta,\eta,p,\theta<1, with \eta\le\sigma, depending only on J, with the following property. For any finite weighted family of nonempty affine alphabets and folded bit proofs, suppose
Draw \xi, a standard Gaussian c\in\R^X, independent uniform x\in X and i\in[m], and all background rows independently and uniformly in D(A_\xi). With probability at least p, the function
has a Fourier coefficient of absolute value at least \theta at an odd frequency of D(A_\xi). Equivalently, the event is
For every folded proof, without any test assumption, one has pointwise
The rest of this Section proves a low-degree correlation estimate. Section 4 turns that estimate into (3.5); the parameter choices in Section 4.6 complete the proof of Theorem 3.2.
3.3 Quantitative smoothing and degree projections
For the rest of this Section fix the following parameters, before choosing m,n:
Choose an integer s\ge1 such that
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
All constants in (3.7)–(3.8) 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
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
The definition is coordinatewise in x. Both projections also act orthogonally in the Hilbert space averaged over the arbitrary weights of \xi.
Lemma 3.3 (Gradient energy and the two cutoffs). Assume \eps_1\le Jb_1 and \eps_2\le Jb_2, and use (3.7)–(3.8). For every m,n\ge2,
Proof. Set Q_B(u)=\E_\lambda f(P_{u,\eta\lambda}(B)). This is a bounded measurable function of u: it is obtained from finitely many threshold signs followed by a function on a finite set. Gaussian convolution and (2.3) give the identity
For fixed \xi,B,c, the functions g_x form an orthonormal family in the joint probability space of (g,\lambda). Bessel’s inequality gives
The individual-coordinate bound in (3.6) follows as well. In particular all gradients used here are square-integrable.
Negating u and changing \lambda to -\lambda negates every table entry almost surely. Indeed, conditional on u, each entry has an independent continuous perturbation of variance \eta^2>0. Folding therefore implies Q_B(-u)=-Q_B(u). Symmetry of g gives F_B(-c)=-F_B(c), so \E_c F_B(c)=0 for every \xi,B. Let f_0(B,c)=f(P_{c,0}(B)), which has absolute value one. Jensen’s inequality and the first test give
The triangle inequality in the joint L^2 space consequently gives \norm{F}_2\ge1-1/8=7/8 and \E F^2\ge49/64>3/4. By the mean-zero Gaussian energy identity (2.2),
proving (3.11). This argument only uses the averaged failure bound.
For the Gaussian cutoff put
Then F_B=T_\rho G_B and |G_B|\le1. If G_B=\sum_I a_I(B)\psi_I, its noise average has coefficients \rho^{|I|}a_I(B). For precision about the derivative, Gaussian integration by parts and the Hermite recurrence give
Integration by parts is legitimate because F_B and its first derivatives are bounded, and a Gaussian times any polynomial has integrable tails. This identifies the actual derivative coefficients with those obtained by formally differentiating the Hermite expansion. Parseval and \sum_I|a_I(B)|^2\le1 now yield, for every \xi,B,
The shift from s+1 to s+2 occurs because differentiating a degree k Hermite polynomial gives degree k-1. This proves (3.12) uniformly in N.
For the row cutoff, apply Bessel’s inequality to the difference of the two representations (3.15), with the same g,\lambda:
Write a=\delta^2/m. Conditional expectation over the row-resampling channel multiplies a constant character on one row by 1, and a nonconstant character by 1-a: on resampling, its uniform average is zero. Independence of rows therefore gives eigenvalue (1-a)^k for row degree k. Stationarity of the channel and Parseval show that a degree-k squared Fourier norm contributes
times that norm to the left side of (3.16). If k>Rm, then ka>R\delta^2\ge1. The elementary inequality (1-a)^k\le(1+ka)^{-1} follows by applying the binomial inequality to (1-a)^{-k}, using (1-a)^{-1}\ge1+a. Hence (1-a)^k<1/2, and the displayed multiplier exceeds one. The total squared Fourier norm of row degrees k>Rm is at most 1/32, proving (3.13).
Finally, commuting orthogonal projections give \E\ip{L}{h}_x=\E\norm{L}_{2,x}^2. Their discarded parts satisfy
Combining this with (3.11) gives \E\norm{L}_{2,x}^2\ge21/32>1/2. Orthogonal projection and (3.6) give the upper bound in (3.14).
3.4 Truth-table differentiation and a product-of-faces correlation
For a real array v on X, define
The second maximum is over the binary face arrays appearing in (3.2); equality of the maxima follows from that definition. In particular \mathfrak d_X(v)\le\norm{v}_{2,x}.
Proposition 3.4 (Low-degree correlation). Fix J and the constants (3.7)–(3.8). For every m,n\ge2 and every finite weighted family of folded proofs satisfying \eps_j\le Jb_j for j=1,2,3, the field L from (3.10) has Fourier row degree at most Rm and Gaussian degree at most s, satisfies (3.14), and obeys
All constants preceding m,n are uniform in their values and in the affine alphabets.
Proof. It remains to prove (3.18). For fixed B define the bounded function on \R^{\C}
Gaussian differentiation in the independent truth-table coordinates gives
In (3.4), the input to this function is t_z=N^{-1/2}\sum_x(c_x+\sigma g_x)(-1)^{z_x}. The chain rule therefore gives the exact representation
There are finitely many table coordinates, and |\partial_{t_z}\Psi_B|\le\eta^{-1}\E|\lambda_z| uniformly in t, so differentiation may pass through the expectation over g.
We bound the absolute coefficients by the third bit test. Condition on \xi,B,c,g and on all coordinates of \lambda other than \lambda_z. The two numbers
do not depend on \lambda_z. If t_z=N^{-1/2}\sum_x(c_x+\sigma g_x)(-1)^{z_x} and \varphi(u)=(2\pi)^{-1/2}e^{-u^2/2}, elementary integration of the one-dimensional Gaussian density yields
Its absolute value is at most 2\mathbf1_{\{f_+\ne f_-\}}. This calculation depends only on the two possible table values at z; it does not require B:A\to\C to be injective. Taking absolute values after the other averages and summing over z gives, with W=\sum_{z\in\C}|\mu_z|,
Thus (3.19) places h in W times the convex hull of the signed codeword arrays \{\pm((-1)^{z_x})_{x\in X}:z\in\C\} (with h=0 if W=0). For every realization it follows that
The large-W contribution can be controlled without a pointwise bound on L. By (3.6), Cauchy–Schwarz, Markov’s inequality, and (3.14),
Since \E\ip{L}{h}_x\ge1/2, we obtain
which is (3.18). The low-degree and energy claims have already been proved in Lemma 3.3.
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 (3.18) 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.
4 From face correlation to an odd row coefficient
Proposition 3.4 gives a low-degree field L with \E\mathfrak d_X(L)\ge1/(4T). We will show that this correlation forces a large odd Fourier coefficient in one row of the original field h, as required by Theorem 3.2. We first choose m large enough to partition the Fourier–Hermite terms of L_x: each nonzero term either has positive degree in c_x, or carries equal odd frequencies in two rows B^i_{x_{-i}} and B^j_{x_{-j}}. Equal frequencies turn the two row factors into a character of their sum. Restriction to a random smaller box will then separate the other variables, allowing the two kinds of terms to be estimated by centering and by a four-corner Fourier identity.
Throughout this Section, \sigma,\delta,\eta,R,s,T are the constants of Proposition 3.4, already chosen independently of m,n and of the affine alphabet. All expectations include the weighted proof index \xi, unless explicitly conditioned on it. We use only averaged test bounds; individual indices need not satisfy those bounds.
Let
be the set of rows. For a family of frequencies \boldsymbol\alpha=(\alpha_r:r\in\mathcal R), write \chi_{\boldsymbol\alpha}(B)=\prod_r\chi_{\alpha_r}(B_r) and S_i=\{y:\alpha^i_y\ne0\}. Thus S=(S_i)_i is the exact row mask, and |S|=\sum_i|S_i| is the row degree. At a fixed proof index, the Fourier–Hermite expansion of the projected field is
This is a finite sum. Coefficients and the row frequency spaces may depend on \xi; the sets of row positions and Hermite indices do not. We select components using only x,I,S. Counting row masks and Hermite indices, without counting the possible values of the nonzero frequencies, will keep the coefficient estimates independent of the alphabet.
4.1 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
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=\one_{\{u_{-i}=v\}}. This is a codeword in \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
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
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
These identities hold separately for every proof index and for every alphabet.
Choose m>s+1 so large that
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:
- (i)
No u with I_u>0 satisfies u_{-i}=x_{-i} or u_{-j}=x_{-j}.
- (ii)
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 (4.4) 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 (4.2) with q=x_{-ij}. Condition (ii) leaves only the two local frequencies, so they are equal. Apply (4.3) to r=(i,x_{-i}). Here k_x=1 and condition (i) makes the Hermite sum zero. Therefore
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
By subadditivity of \mathfrak d_X and Proposition 3.4,
It will suffice to show, under failure of the asserted row-atom conclusion, that every summand is strictly less than d_0.
4.2 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,
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
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
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 (4.5) give, for each x\in Y, a function V_x:D(A)\to\R, determined by this background, such that
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 (4.10) says
4.3 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
This is a function only of the indicated background and the proof index. Its pointwise upper bound is \sqrt N/\sigma.
Lemma 4.1 (Uniform transfer through the selected projection). Let Q_x^Y select any collection of complete exact-mask/Hermite components with |I|\le s, using only x,Y,I,S. For a fixed axis i let q_{x,i}^Y be the maximum odd row coefficient of Q_x^Yh_x in r=(i,x_{-i}), with the other rows and c held fixed. Then
The estimate is valid for every weighted distribution of proof indices.
Proof. For a row t, write E_t for averaging that row uniformly. The projection onto an exact mask S\subseteq\mathcal R is
The projection onto the Hermite index I is
There are 2^M masks and \binom{N+s}{s} multi-indices with |I|\le s. Thus Q_x^Y is a sum of at most their product of operators P_SH_I.
Taking a Fourier coefficient in the distinguished row r commutes with all the other row averages. If r\notin S, the average E_r annihilates every odd coefficient. If r\in S, the factor \operatorname{Id}-E_r leaves such a coefficient unchanged. Expand the remaining factors \operatorname{Id}-E_t into signed averages; there are at most 2^M terms. Each term averages some of the other rows without changing the distinguished frequency. For one such term, its maximum odd coefficient is consequently bounded by
This follows by moving the maximum inside the absolute-value integral; no sum over row frequencies is introduced. At fixed \xi,x, average the output c and all the other output rows. Uniform row averages preserve the product measure, \E|\psi_I(c)|\le1, and Cauchy–Schwarz gives
The bound is independent of I,S,Y. Summing at most 4^M\binom{N+s}{s} expanded terms proves the corresponding bound at fixed \xi,x,Y. Finally apply Cauchy–Schwarz to the probability measure on \xi,Y,x\in Y, and use the uniform marginal of x. This proves (4.14), including arbitrary weights on \xi. Only counts of positions, masks and Hermite indices entered the constant.
Suppose, for a contradiction, that the row-atom conclusion in Theorem 3.2 fails for positive constants p,\theta to be chosen at the end. In this notation the failed assertion is
Since i is uniform, for each fixed axis i this event has probability less than mp. The pointwise bound on a_{x,i} gives
This is only an averaged estimate in x,\xi, which is exactly the estimate required in Lemma 4.1.
For a retained pair class use Q_x^Y=Q_x^{ij,Y} and the distinguished axis i. From (4.12), 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 (4.14)–(4.15) imply
for every \gamma>0. The probability here is over a uniform point of Y and its slice background.
4.4 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
For class 0, use its conditional description above and set
Here the conditional expectation fixes all rows and the Gaussians outside Y. Since \E_{c_x}v^0_x=0, inequality (4.17) bounds both the clipping loss and the absolute value of the subtracted mean. Thus
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:
- (i)
Set the slice to zero if \|V_x\|_2>H.
- (ii)
Set it to zero if q_x>\gamma.
- (iii)
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
For the second discard, Cauchy–Schwarz, (4.13) and (4.16) give the bound
Indeed its loss is at most \E\E_{x\in Y}\nu_x\one_{\{q_x>\gamma\}}, regardless of whether the first discard has already occurred. The last clipping operation costs at most \sigma^{-2}/A_0 by (4.17). Consequently
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,
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.
4.5 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 [5, Section 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\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.
Lemma 4.2 (Box Cauchy–Schwarz). For every real array v,
In particular the right side is nonnegative.
Proof. Fix face multipliers a_j:Y_{-j}\to[-1,1]. We describe each Cauchy–Schwarz step. At stage k, double the first k coordinates and keep the last m-k coordinates single. For \omega\in\{0,1\}^k, write
and define
Thus A_0 is the original correlation and A_m is the right side of (4.22). In A_{k-1}, the product of factors a_k is independent of the single coordinate u_k and has absolute value at most one. Put the average over u_k innermost and apply Cauchy–Schwarz over all outer variables, removing that product. The result is the average of the square of the remaining inner average. Expanding this square with two independent values u_k^0,u_k^1 gives exactly A_k. Therefore
Iterating yields |A_0|^{2^m}\le A_m, as well as nonnegativity of A_m. Taking the maximum over the finitely many face signs proves the assertion.
Apply Lemma 4.2 pointwise to a processed random field w, before averaging any of its randomness. Write Q=2^m. By Jensen’s inequality,
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
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
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.
Figure 1: A square after fixing the slice background. The four rows r_0,r_1,s_0,s_1 are independent, but their four sums satisfy one parity relation. Fourier expansion therefore leaves one common frequency. Different squares of a collision-free cube use disjoint rows.
For four possibly different real slice functions W_{ab}, direct Fourier expansion gives
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 (4.25) is at most
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 (\eps_0^2H^2)^{2^{m-2}}. Combining this with the collision bound and (4.23), and using (a+b)^{1/Q}\le a^{1/Q}+b^{1/Q} for a,b\ge0, gives
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.
4.6 Choosing parameters and completing inner decoding
For any two fields on a fixed box, |\mathfrak d_Y(u)-\mathfrak d_Y(v)|\le\E_{x\in Y}|u_x-v_x|. Thus (4.8), localization, the processing losses, and (4.27) imply, for each pair class,
For class 0, the corresponding bound is
Proof of Theorem 3.2. The smoothing parameters were fixed in Proposition 3.4. Choose m as in (4.4), define d_0 by (4.6), and set e=d_0/10. Make the following successive choices, each with strict slack:
- 1.
Choose a positive integer H with \sigma^{-2}/H<e.
- 2.
Choose a positive rational \gamma with H\gamma<e^2/4.
- 3.
Choose a positive integer A_0 so large that 2\sigma^{-2}/A_0<e and H^3/A_0<e^2/4. These choices give \sqrt{H(\gamma+H^2/A_0)}<e.
- 4.
Choose an integer \ell\ge2 so large that 2A_0(m/\ell)^{1/2^m}<e.
- 5.
Choose an integer n>\ell so large that \sigma^{-1}\sqrt{(s+Rm)\ell/(n-1)}<e.
- 6.
Now N=n^m, M=mn^{m-1} and C_0=4^M\binom{N+s}{s} are fixed. Choose positive rationals p,\theta<1 so small that
\theta^2+\frac{mpN}{\sigma^2} <\frac{e^4\sigma^4\gamma^2}{C_0^2}.This makes e_{\mathrm{atom}}<e.
All choices are finite and use explicit inequalities. Roots in these inequalities can be removed by raising positive quantities to integer powers, so rational arithmetic and integer search suffice. Neither the alphabet size nor the distribution of the proof index enters them.
If the row-atom assertion failed for these p,\theta, the preceding argument would apply. Each pair-class correlation in (4.28) would be less than 6e<d_0, and the class-0 correlation in (4.29) would be less than 3e<d_0. Summing over the 1+\binom m2 classes would give
contradicting (4.7). This proves the claimed probability at least p of an odd conditional coefficient of magnitude at least \theta. The pointwise bound on h_x is (3.6), completing Theorem 3.2.
5 An outer game with affine hints
This Section constructs the outer game and proves the two properties used in Section 6: soundness with shared affine hints, and approximate joint uniformity of pulled-back affine functions.
Smooth equation–variable sampling and Fourier decoding have antecedents in Khot and Safra [11, Sections 3.2–3.4 and 5.2]. Khot, Minzer and Safra [10, Sections 3.3–3.4] use shared linear information and zero-advice coordinates; Dinur et al. [3, Section 5.2, Lemma 5.4] give a related shared-subspace formulation. We prove both properties for the exact questions and hints defined below.
Let \mathcal E=(E^{(1)},\ldots,E^{(M_0)}) be the nonempty uniform equation list supplied by Theorem 2.2. An equation question E consists of its ordered three variable names v(E,1),v(E,2),v(E,3) and its right-hand side \tau_E\in\F_2. Thus it asks that
The list may have repeated equations, and variable names may repeat within an equation. Sampling is uniform over list entries, but equal equation questions have identical encodings: an index distinguishing equal list entries is not part of a player’s question.
5.1 Questions, fresh slots, and canonical functions
For an equation E, put
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
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
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
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
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
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
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.
5.2 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 \F_2^3 with invalid answers rejected, so the answer sizes are at most eight and two.
Lemma 5.1. If no assignment satisfies more than 3/4 of the equation list, the ordinary equation-versus-variable game has value at most 11/12. Consequently its ordinary r-fold repetition has value at most c^r, for the effective universal constant c<1 of Theorem 2.3, for every r\ge0.
Proof. Fix a deterministic second strategy. Its bit for each variable name defines a global assignment. On at least 1/4 of the sampled equations this assignment violates the equation. Every valid first answer to one of these equations disagrees with this assignment in at least one of the three positions, so a uniform position detects disagreement with probability at least 1/3. An invalid answer is rejected in every position. The overall failure probability is therefore at least 1/12. Repeated variable names do not affect the argument: equality at all three positions would still give precisely the violated assignment on that equation. The repeated bound follows from Theorem 2.3; its hypotheses depend only on this value bound and the two answer sizes.
Lemma 5.2 (Hint soundness). Suppose no assignment satisfies more than 3/4 of the equation list. For every q\ge0 and t\ge t_0\ge1, the value of the game with q affine hints is at most
The bound also applies to strategies using arbitrary independent shared or private randomness. In particular, for fixed q and any prescribed rational s>0, an effective choice of t_0 makes the bound strictly less than s, simultaneously for every t\ge t_0, every equation-list size, and every completeness parameter in Theorem 2.2.
Proof. Use the unrestricted slots of A_V to generate the hints. Let z_j denote the one-bit coordinate when j\in H, and let z_{jp}, p\in[3], denote the three coordinates when j\notin H. A uniform affine form has the unique expression
All coefficients and constants in these expressions, for 1\le\ell\le q, are independent uniform bits. They can be sampled after H and before any equation or position, because the abstract slots in this expression depend only on H. Thus their distribution is independent of all sampled equations and positions.
Define the active coordinates by
For each j\in H its vector of q coefficients is uniform in \F_2^q, independently across j. Consequently
Conditional on H, the active set and the coefficient bits are independent of the equation and position samples. The equations are also independent of H. When q=0, all hidden coordinates are active and (5.4) means |A|=t_0 deterministically.
For the analysis give both players the following additional information: H, every coefficient and constant in (5.3), and all equation samples and all chosen positions outside A. Denote this background by W. It determines A without inspecting its equation or position samples. Conditional on any possible W, the pairs
are still independent samples of a uniform equation-list entry and an independent uniform position in [3]. This follows directly from the product sampling distribution: once H and the coefficients are fixed, A is fixed, and conditioning on samples in its complement does not change the samples in A.
We now show that, for fixed W, ordinary repeated-game questions in the active coordinates simulate each player’s original information exactly. List A in increasing order, so that its |A| coordinates can be identified with an ordinary repetition.
- (i)
The first player receives the active equation questions (E_j)_{j\in A}. Together with W, these reconstruct all of U and hence A_U. For every hint the active summands in (5.3) are identically zero. On any a\in A_U, therefore,
(\pi_e^*L_\ell)(a)=\kappa_\ell+ \sum_{j\in H\setminus A}\beta_{\ell j}(a_j)_{p_j}+ \sum_{j\notin H}\sum_{p=1}^3\beta_{\ell jp}(a_j)_p.Every position appearing on the right is in the background. Thus the first player can compute the canonical truth table of each pulled-back hint, without receiving any active p_j or active variable question from the second side. Although the domain A_U depends on active equations, these are exactly the first player’s own repeated-game questions.
- (ii)
The second player receives only the active variable names (v(E_j,p_j))_{j\in A}. Together with W and the tags specified by H, these reconstruct V and A_V. Formula (5.3), whose active coefficients vanish, computes every direct hint on this alphabet. Thus the second player can compute its canonical truth table without receiving an active equation or the chosen position within one.
These reconstructions also explain why the representation of a hint matters. No metadata attached to a zero summand is present in the actual message. Restricting the zero function to an affine domain cannot create an offset or convey a hidden position. All nonzero contributions and their possible affine offsets are determined by the background and the receiving player’s own question.
Apply the original response functions to the reconstructed information, and restrict their answers to the active coordinates. This defines a strategy for the ordinary |A|-fold repeated game, with W fixed as a parameter. Acceptance of the full outer sample implies acceptance in every active coordinate, since (5.1) imposes exactly the ordinary equation-versus-variable comparison there. By Lemma 5.1, its conditional probability is at most c^{|A|}; for A=\varnothing this is the trivial bound one.
This reasoning includes coincidences between variable names or equation questions in different coordinates, and coincidences with the exposed background. Independent samples may coincide without ceasing to have a product distribution. Once W is fixed, the simulated strategies may use all information about such coincidences obtainable from their respective questions, just as arbitrary strategies for ordinary repetition may do. No equality between fresh answer slots, nor any further information about an active question on the opposite side, has been supplied.
Average over W and use (5.4). The binomial generating function gives
One may first fix all independent random seeds of the players, apply the bound, and then average; this covers the stated random strategies.
Finally replace c, if necessary, by an effectively chosen rational number \bar c with c\le\bar c<1. Successively multiplying the rational number 1-2^{-q}(1-\bar c)<1 finds an integer t_0 whose power is strictly less than s. This finite procedure is independent of t, the instance, and its completeness error. It supplies the asserted effective choice.
5.3 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 \TV(\mu,\nu)=\frac12\sum_x\abs{\mu(x)-\nu(x)}.
Lemma 5.3 (Joint smoothness). Fix any actual first question U, integers d\ge1 and t\ge t_0\ge1, and draw the remaining outer sample conditional on U. Draw L_1,\ldots,L_d independently and uniformly from D(A_V). Then
The bound is uniform in U and the equation list, including repeated variable names and zero-dimensional local alphabets. For fixed d,t_0 and positive rational \Delta, an effective integer t\ge t_0 makes the right-hand side strictly less than \Delta.
Proof. Write A_j=A(E_j) and r_j=\dim A_j\le2. Choose, using E_j alone, an affine origin o_j\in A_j and an injective linear map T_j:\F_2^{r_j}\to\F_2^3 with image the translation space of A_j. Thus every label has a unique expression
For example, lexicographic search and binary Gaussian elimination make these choices canonical and effective. In these product coordinates a form on A_U consists of one constant bit and a linear part in each coordinate group \F_2^{r_j}. A d-tuple of forms consequently consists of d constant bits and groups
Generate the d forms by their independent raw coefficients and constants on the unrestricted slots of A_V, as in (5.3). After pullback, their constant bits are the original independent uniform constants plus offsets determined by the other coefficients, the positions, and the origins o_j. Conditional on all those other data, this addition is a translation of \F_2^d. Hence the resulting constants are jointly uniform and independent of every linear part, of H, and of the chosen positions. Their common uniform factor contributes no total-variation distance, so it suffices to analyze the joint linear parts (\xi_1,\ldots,\xi_t).
Fix H. If j\notin H, a single form has independent uniform coefficient vector w\in\F_2^3 on its three raw slots; its pulled-back linear part is T_j^{\mathsf T}w. The map T_j^{\mathsf T} has rank r_j and is onto \F_2^{r_j}. Every fiber therefore has the same size, so its output is uniform. All d forms in this group are independent, and their joint law is the uniform law \mu_j on (\F_2^{r_j})^d.
If j\in H, condition first on its chosen position p_j. The \ellth form has a uniform bit coefficient \beta_{\ell j} on that slot, so its linear part is \beta_{\ell j}v_{j,p_j}, where v_{j,p} is the linear part of the pth coordinate of o_j+T_ju_j. Average over the single uniform choice of p_j shared by all d forms, to obtain a distribution Q_j on (\F_2^{r_j})^d. Its density \rho_j with respect to \mu_j satisfies
Indeed, every point of this finite space has uniform mass 2^{-r_jd}, whereas its Q_j mass is at most one. This argument allows a position’s linear part to be zero or to coincide with another position’s linear part. If r_j=0, the space is a singleton and \rho_j=1.
For fixed H, the linear-part groups are independent across j: their coefficients are independent, and the positions in distinct hidden coordinates are independently sampled. Fresh slots give this independence even when variable names in different equations coincide. Relative to the product uniform measure \mu=\prod_{j=1}^t\mu_j, their joint density is therefore
The densities \rho_j depend on U,d,j but not on the other elements of H. Since H is uniform and independent of U, the desired mixed density is g=\E_H g_H.
Let H' be an independent uniform t_0-element subset of [t]. If H\cap H'=\varnothing, independence of the coordinate groups and (5.6) give \E_\mu g_Hg_{H'}=1. For every H,H', the pointwise bound g_Hg_{H'}\le2^{4dt_0} gives the sufficient bound \E_\mu g_Hg_{H'}\le2^{4dt_0}. Moreover, for fixed H,
Since \E_\mu g=1, it follows that
Cauchy–Schwarz now yields \TV(g\mu,\mu)=\frac12\E_\mu\abs{g-1} \le\frac12\sqrt{\E_\mu(g-1)^2}, proving (5.5), including the independent uniform constants.
All estimates used only r_j\le2, so the bound is uniform as asserted. For effectiveness, it is enough to choose an integer
The right-hand side is an explicitly computable rational number for fixed d,t_0,\Delta. No parameter depending on U occurs in this choice.
Remark 5.4. Because (5.5) is uniform in U, it may be averaged over any distribution of U and any extra randomness independent of the outer sample. In particular, if a bounded statistic is chosen as a function of U and some of the pulled-back forms, one may apply Lemma 5.3 to the joint collection of all forms used by that statistic. For a statistic bounded in absolute value by B, the change in expectation is at most 2B times the displayed total-variation bound. This does not assert uniformity of one form conditional on previously revealed forms.
Finally, these outer games are explicit finite objects. Their complete sampling space has
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.
6 Composition and soundness of the bit comparisons
We now compose the inner test with the outer game. The main issue is that the first player’s Fourier truncation depends on the shared background. The joint form of Lemma 5.3 is designed to retain that dependence.
Proposition 6.1 (A gap for bit comparisons). For every fixed integer J\ge20, effective choices of constants give a four-test comparison system with the following properties. It is constructed from the uniform equation list in Theorem 2.2, for a fixed completeness error \zeta>0 chosen by the construction. Every test compares two bits in folded proof tables, and its contribution to cost is its failure probability divided by a positive rational budget b_j. In the YES case there are proof tables of cost at most 4; in the NO case every collection of proof tables has cost greater than J. Alphabet sizes are bounded by effective constants depending only on J, and all local numerical parameters depend only on J.
Proof. Apply Theorem 3.2 with J, taking its atom constants p,\theta to be positive rationals by decreasing them if necessary. Set
The counts t_0\le t of the outer game will be chosen below. Give each actual first question U a folded bit proof f_U on A_U, and each actual second question V a folded bit proof f_V on A_V. The same question always uses the same proof; an occurrence of a hidden variable is never separately indexed by its unrevealed equation or position.
The first three tests are those of Theorem 3.2, applied to f_V under the marginal distribution of V. For the fourth test sample a full outer edge e, an independent uniform face array B over D(A_V), and the Gaussian query table P=P_{c+\sigma g,\eta\lambda} on the common code \C. Compare
Here \pi_e^* acts on every entry of B. The Gaussian table on \C is literally the same on both sides, even if distinct codewords have identical pullbacks at one alphabet. Let b_4>0 be a small rational budget, to be fixed shortly, and define
Suppose, toward a contradiction in the NO case, that \Cost(f)\le J. Each of the first three failure bounds required by Theorem 3.2 then holds, including the random index V. Draw an outer edge e, a uniform i\in[m] and x\in X, and independent c. The q rows other than B^i_{x_{-i}} will serve as the independent uniform background forms allowed in Lemma 5.2. Put them in a fixed order depending only on the public i,x. The two players receive these rows on their own alphabets, and use c,i,x as additional public randomness, independent of the game. From their respective information they form the one-row functions
The notation in (6.3) simply means filling the missing entry of the received array with a free argument. The first player needs no knowledge of e or V to define H_U. Both functions are bounded in absolute value by M_*.
The two row functions are close. For fixed e,B,c, apply (2.3) to the difference between the two bits in (6.1), using the same g,\lambda. Bessel’s inequality for the orthonormal functions g_x gives
Averaging e,B,c bounds the right-hand side by 4Jb_4/\sigma^2. Integrating the missing row in (6.2) restores a fully independent uniform array B, regardless of i,x. Thus
Choose a positive rational b_4 so small that
Markov’s inequality then makes the norm in (6.4) less than \theta/4, except on an event of probability less than p/4.
Diffuse first-side frequencies remain small after pullback. Choose a positive rational u<1. At each first-player information state, let r_U be H_U with all Fourier terms of magnitude at least u removed. Parseval and the bound \abs{H_U}\le M_* give
For the last bound, each removed coefficient satisfies \abs{a}\le\abs{a}^2/u.
We claim that if the total-variation bound of Lemma 5.3 for d=q+3 is at most \Delta, then
To prove this, fix U and the independent public randomness c,i,x. For fixed background and e, identity (2.1) expresses the Fourier sum on the left as the average of
where a,b,c' are independent uniform forms on A_V. Pullback is linear on the spaces of affine forms, so its fourth argument is determined by the first three. The entire expression, including the choice of r_U, depends only on U,c,i,x and the q+3 pulled-back forms consisting of the background and these three additional arguments. It is bounded by M_r^4 in absolute value. Replace their joint distribution by independent uniform forms on A_U. Lemma 5.3 changes the expectation by at most 2\Delta M_r^4. Under the replacement, conditioning on the background fixes r_U, and (2.1) and (6.6) bound its expectation by u^2M_*^2. Averaging proves (6.7). This argument uses joint total variation; it does not conditionally replace the missing row while keeping a nonuniform background fixed.
First choose u>0 rational sufficiently small, and then require a sufficiently small positive rational \Delta, so that
By (6.7) and Markov’s inequality, no Fourier coefficient of r_U\circ\pi_e^* has magnitude at least \theta/4, except on an event of probability less than p/4.
Local lists give a strategy for the outer game. Theorem 3.2 supplies an odd coefficient \beta of H_V with magnitude at least \theta with probability at least p. Combining that event with the two preceding estimates leaves probability at least p/2. On this event, the coefficient of H_U\circ\pi_e^* at \beta has magnitude greater than 3\theta/4, since every coefficient is bounded by the L^2 norm of a function. The coefficient of its remainder has magnitude less than \theta/4. Consequently the pullback of the removed part has a nonzero coefficient at \beta. At least one removed frequency \alpha therefore satisfies
This conclusion permits multiple frequencies to have the same image: a nonzero sum has at least one nonzero summand. Since \pi_e^*(1)=1 and \beta is odd, such an \alpha is odd as well.
The first player lists the odd frequencies of H_U of magnitude at least u, and the second lists the odd frequencies of H_V of magnitude at least \theta. These lists are functions of their own information. By Lemma 2.1, they are lists of labels, and on the event just described they contain a pair agreeing under \pi_e. Their sizes are at most M_*^2/u^2 and M_*^2/\theta^2. Choose uniformly from nonempty lists and choose any fixed label when a list is empty. With independent private randomness, the resulting strategy succeeds with probability at least
The strategy is used only to bound the value of a finite game. Its Fourier computations need not be efficient, and its independent continuous public randomness does not raise the game value above the maximum deterministic value.
Parameter order and contradiction. All quantities so far depend only on the inner constants and J. Choose t_0 effectively so that the upper bound in Lemma 5.2 is strictly below s_* for the fixed q. Then choose t\ge t_0 so large that Lemma 5.3 gives the required \Delta for d=q+3. Equation (6.9) contradicts the hinted-game upper bound, proving that no NO-case proof has cost at most J.
Finally choose a positive rational \zeta with t\zeta\le b_4 and invoke Theorem 2.2. Its NO bound is always 3/4, independently of \zeta, so this last choice does not affect the repetition constants. In the YES case let a global assignment satisfy at least 1-\zeta of the equations. Give each V its values at all requested slots. Give U these values whenever all its equations are satisfied, and choose any label in A_U otherwise. The first labels lie in their required affine alphabets, and the labels agree under \pi_e except on an event of probability at most t\zeta. Use evaluation proofs at these labels. Lemma 3.1 bounds each of the first three normalized costs by one; agreement of labels makes the fourth comparison exact, so its normalized cost is also at most one. This proves the YES bound.
The order of choices is, explicitly,
All strict inequalities can be imposed with rational slack and integer searches using the displayed bounds. In these searches M_*^2=N/\sigma^2 is rational; the possibly irrational quantity M_r may be bounded above by the rational number N/\sigma+N/(\sigma^2u) before choosing \Delta. The complete construction therefore has effective constants independent of the input length.
7 A deterministic finite reduction to simple graphs
Fix an integer K\ge2, put J=10K, and make the effective parameter choices in Proposition 6.1. Write \Cost_\infty for its cost, and put
This is a positive rational constant depending only on K. The Gaussian randomness will now be replaced by one finite rational distribution. We retain the full joint distribution of the queried sign tables.
7.1 Rational Gaussian sign tables
Let c,g\in\R^X and \lambda\in\R^{\C} have independent standard Gaussian coordinates. Define the two tables on \C
Their pair is a random element of a finite set of size 2^{2|\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.
Lemma 7.1 (Effective finite comparisons). There is a deterministic construction, with all preliminary work depending only on K, of a finite rational replacement for the four tests such that
Consequently its minimum cost is less than 9/2 in the YES case, and every proof has cost greater than 10K-1/2 in the NO case. The rational distribution replacing (T_0,T_1) has a positive integer common denominator depending only on K, computed by the construction.
Proof. We give a deterministic rational approximation with any prescribed rational accuracy 0<\eps<1/4. Set
The S unforced threshold inputs are linear forms in a vector Z\in\R^d of independent standard Gaussians. Each input for T_0 has variance 1, and each input for T_1 has variance 1+\sigma^2+\eta^2. Its coefficient vector has \ell^1 norm at most
These bounds do not require nonsingularity of the joint distribution of the threshold inputs.
Choose an integer T_G\ge1 such that
The probability \alpha that Z\notin[-T_G,T_G]^d is at most d/T_G^2, by the second-moment bound in each coordinate and a union bound. Partition [-T_G,T_G] into L equal intervals of length h=2T_G/L, with rational midpoints. Choose the integer L large enough that
Endpoint conventions for the intervals are immaterial to their Gaussian masses. Rounding an interior vector to its cell midpoint changes any threshold input by at most Ah/2. If the corresponding signs change, the original threshold input has absolute value at most Ah/2. A centered Gaussian of variance at least one has density at most one, so the probability of this event for any one threshold is at most Ah. The union bound over all S thresholds is therefore at most SAh. In particular, all unrounded ties have probability zero.
For completeness, this estimate can be combined with truncation without losing control at the boundary. Couple Z with a vector Y as follows: keep Y=Z when Z is in the cube, and otherwise draw Y independently from the Gaussian conditioned on the cube. Then Y has exactly that conditional law. On the event that Z is outside, charge the full probability \alpha; on its complement use the preceding sign-change estimate. Hence the law of the original joint sign table and the law obtained by rounding the conditioned Gaussian differ in total variation by at most
We next compute rational approximations to the conditioned Gaussian cell masses, including their exact normalization. This step uses no real-number oracle. Put U=T_G^2/2, and choose an integer r\ge0 such that
This is a terminating search with rational comparisons. Indeed e_{r+1}/e_r=U^2/((2r+2)(2r+3)), so after an effectively found index the ratio is at most 1/2. Define the rational polynomial
Taylor’s remainder for e^{-u}, with u=v^2/2\ge0, gives
In particular Q_r is strictly positive on the interval. For each grid interval I=[a,b], compute the rational number
Both integrals are evaluated by the rational antiderivative
Thus the w_I are positive rationals and their sum is exactly one.
Here is a quantitative error bound for these cell masses. Write g(v)=e^{-v^2/2} on [-T_G,T_G], let Z_g=\int_{-T_G}^{T_G}g, and let E_r=\int_{-T_G}^{T_G}(Q_r-g). Since T_G\ge1 and e^{-u}\ge1-u for u\ge0,
The probability density Q_r/(Z_g+E_r) is a mixture of g/Z_g and the normalized nonnegative residual Q_r-g, with residual mixture weight E_r/(Z_g+E_r) (if E_r=0 the densities coincide). Their total variation distance is therefore at most 2T_G e_r. The Gaussian conditioned on the cube is a product of these one-dimensional conditioned laws. Taking products increases the total variation error by at most the sum of the coordinate errors, as follows by replacing the coordinates one at a time. Rounding to the grid cannot increase total variation. Consequently the grid distribution assigning mass \prod_{i=1}^d w_{I_i} to a cell has total variation distance at most 2dT_G e_r<\eps/4 from the rounded conditional Gaussian law. Together with (7.3), this proves error less than \eps for the complete joint sign table.
Every sign at a rational midpoint is also computed exactly. A T_0 input has the sign of a rational number. Multiplying a T_1 input by \sqrt N>0 expresses it as
If a,b have the same sign, or one is zero, its sign is immediate. If their signs are opposite, compare the rationals a^2 and Nb^2; the term of larger magnitude determines the sign, and equality is an exact zero. Declare the sign of zero to be +1. This also handles square N. Thus grid ties and all algebraic comparisons use finite rational arithmetic.
Choose a common denominator Q_1 for the finitely many rationals w_I, for example the product of their reduced positive denominators, and put Q=Q_1^d. Every cell probability is an integer multiple of 1/Q. Enumerate the L^d cells, compute their complete sign-table pairs, and add the integer numerators for cells giving the same pair. This gives an explicit rational law \widehat\mu for (T_0,T_1) with denominator Q. The code \C, the grid, the polynomial, these numerators, and all sign classifications are computed from the fixed parameters. Their complete enumeration and the bit operations on their rational numbers are finite work depending only on K and \eps.
Finally take \eps=1/(8(1+W)). For each fixed outer sample and each fixed collection of finite random choices in a test, its failure indicator for any fixed proof is a function of the joint table with values in \{0,1\}. Replacing its law by \widehat\mu changes its expectation by less than \eps. Averaging the finite choices and the outer sample preserves this bound. It follows simultaneously for every proof f that
No union bound over proofs is involved. Applying Proposition 6.1 gives the two claimed finite cost bounds.
7.2 Numerical multiplicities and canonical proof variables
Let M_0\ge1 be the length of the uniform equation list from Theorem 2.2. The rounding needed to obtain that list was included in its proof. Set
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 7.1. 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
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
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
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
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
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
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 (7.9) proves exact equality between weighted demand cost and \Cost_{\mathrm{fin}}, for every assignment, including these cases.
7.3 Exact realization by an unweighted simple graph
Lemma 7.2 (Path realization). The finite rational comparison system can be transformed deterministically into a simple undirected unweighted graph G with
The graph has O_K(M_0^t) vertices and edges and is constructed in polynomial time, including bit complexity, for fixed K.
Proof. Start with a vertex for each sign variable. For every unit of integer multiplicity in (7.10), join its endpoint vertices by a path of length four for an equality demand and length three for an inequality demand. See Figure 2. All internal vertices are fresh for that unit demand. If the two endpoints coincide, this prescription means respectively a four-cycle through three fresh vertices or a triangle through two fresh vertices.
Figure 2: Each unit demand becomes a path with fresh internal vertices. For fixed endpoint signs, its minimum uncut cost is zero if the demand holds and one otherwise. Identifying the endpoints gives a four-cycle or a triangle and handles self-demands with the same exact cost.
For an ordinary path with L edges, write the vertex signs along it as x_0,\ldots,x_L, and let r be the number of its uncut edges. Exactly L-r adjacent pairs have opposite signs. Hence
When the prescribed relation holds, alternating signs from the first endpoint give r=0 and reach the prescribed last sign. When it fails, (7.12) rules out r=0; making exactly one adjacent pair equal and alternating on all other edges reaches the prescribed last sign and gives r=1. The same argument with x_L=x_0 proves the assertion for coincident endpoints. A four-cycle has minimum zero, as required by a self-equality; a triangle has minimum one, as required by a self-inequality. Thus each gadget has conditional minimum equal to the failure indicator of its demand.
For any fixed signs on the original vertices, its gadgets can attain these minima independently because their internal vertices are disjoint. Conversely any sign assignment on the graph pays at least the sum of these conditional minima. Minimizing over the original signs and using (7.9) proves (7.11), with no additive term.
No gadget has a loop or a repeated edge. Within a gadget all its internal vertices are distinct; the coincident-endpoint cases have lengths at least three. Between gadgets an edge cannot be repeated, since every edge contains a vertex internal to its own gadget. The construction therefore gives a simple undirected graph and assigns every edge unit weight.
There are at most 2H_KM_0^t actual questions, and a constant number depending only on K of sign variables at each. A gadget introduces at most three vertices and four edges. Equation (7.8) therefore proves the stated size bound. All actual questions and query tables can be identified by deterministic comparisons or sorting of their canonical encodings. Equality of variable names, construction of the affine alphabets, and table pullback require a polynomial amount of work per outer sample; the only unbounded strings are names from the polynomial-size starting instance. The sample count is polynomial for fixed t. The integers in (7.7) and (7.8) have O_K(1+\log M_0) bits. Explicitly writing their multiplicities costs O_K(M_0^t) iterations, and vertex identifiers have O_K(1+\log M_0) bits. These observations include the cost of constructing the vertex and edge lists and all required integer arithmetic.
7.4 The strict gap and algorithmic consequences
Proof of Theorem 1.1. Given a 3SAT instance, perform the deterministic reduction in Theorem 2.2 with the rational completeness error chosen by Proposition 6.1. It supplies the nonempty uniform list of length M_0. Carry out Lemmas 7.1 and 7.2, compute D_0 by (7.7), and output the graph together with
This is a positive integer, computed without knowledge of the optimum. In the YES case these Lemmas give
In the NO case they give
where the second inequality holds for every K\ge2.
All parameter searches in the preceding sections use the displayed effective inequalities. The additional integer searches, rational integrations, cell enumerations, and sign-table construction in this Section are also algorithms. The reduction performs this preliminary work itself; no table or numerical advice is supplied to it. Its cost is a finite constant for fixed K. The starting reduction has polynomial work and output length, and Lemma 7.2 establishes polynomial work and output length for every subsequent step. The integer k has O_K(1+\log M_0) bits. Composition is therefore a deterministic polynomial-time many-one reduction with all the graph properties and the strict positive-threshold gap in the statement.
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\OPT_{\mathrm{uncut}}(G) would decide 3SAT: 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=\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 3SAT in \RP, and composing with deterministic reductions to 3SAT gives \NP\subseteq\RP. The randomized conclusion is therefore the latter containment.
7.5 Minimum 2CNF clause deletion
Proof of Corollary 1.2. Given G=(V,E), introduce a variable x_v for each vertex and, for each edge uv, the two clauses
Call the resulting formula F_G. Equal endpoint values falsify exactly one of these clauses, while unequal values satisfy both. Thus, for every assignment a and S_a=\{v:a(x_v)=1\},
Deleting an assignment’s false clauses gives a feasible deletion set of the same cost. Conversely, from every feasible deletion set D, a polynomial-time 2SAT algorithm finds an assignment a satisfying F_G\setminus D. Every original clause it falsifies belongs to D, so \Uncut_G(S_a)=\operatorname{unsat}(F_G,a)\le\abs{D}. Consequently,
Fix C>1 and choose a fixed integer K\ge\max\{2,C\} in Theorem 1.1. The construction has \abs{V} variables and 2\abs{E} clauses and preserves the gap at the same binary-encoded integer k\ge1: \OPT_{\rm del}(F_G)\le k if the source formula is satisfiable, and \OPT_{\rm del}(F_G)>Kk otherwise. A C-approximation returns a feasible deletion set with \abs{D}\le Ck\le Kk in the former case, whereas every feasible deletion set has \abs{D}>Kk in the latter. Comparing its size with the integer Kk therefore decides 3SAT in polynomial time.
References
- [1]Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(\sqrt{\log n}) Approximation Algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut Problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 573–581, ACM, 2005. doi:
10.1145/1060590.1060675. doi:10.1145/1060590.1060675. - [2]Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability—Towards Tight Results. SIAM Journal on Computing, 27(3):804–915, 1998. Preliminary version in FOCS 1995. doi:
10.1137/S0097539796302531. doi:10.1137/S0097539796302531. - [3]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a Proof of the 2-to-1 Games Conjecture?. Theory of Computing, 21(11):1–50, 2025. doi:
10.4086/toc.2025.v021a011. doi:10.4086/toc.2025.v021a011. - [4]Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42(6):1115–1145, 1995. doi:
10.1145/227683.227684. doi:10.1145/227683.227684. - [5]W. Timothy Gowers. Hypergraph Regularity and the Multidimensional Szemerédi Theorem. Annals of Mathematics, 166(3):897–946, 2007. doi:
10.4007/annals.2007.166.897. doi:10.4007/annals.2007.166.897. - [6]Johan Håstad. Some Optimal Inapproximability Results. Journal of the ACM, 48(4):798–859, 2001. doi:
10.1145/502090.502098. doi:10.1145/502090.502098. - [7]Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations. Theory of Computing, 13(19):1–51, 2017. doi:
10.4086/toc.2017.v013a019. doi:10.4086/toc.2017.v013a019. - [8]Thomas Holenstein. Parallel Repetition: Simplifications and the No-Signaling Case. Theory of Computing, 5(8):141–172, 2009. doi:
10.4086/toc.2009.v005a008. doi:10.4086/toc.2009.v005a008. - [9]Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. SIAM Journal on Computing, 37(1):319–357, 2007. doi:
10.1137/S0097539705447372. doi:10.1137/S0097539705447372. - [10]Subhash Khot, Dor Minzer, and Muli Safra. On Independent Sets, 2-to-2 Games and Grassmann Graphs. Theory of Computing, 21(10):1–55, 2025. Preliminary version in STOC 2017. doi:
10.4086/toc.2025.v021a010. doi:10.4086/toc.2025.v021a010. - [11]Subhash Khot and Muli Safra. A Two-Prover One-Round Game with Strong Soundness. Theory of Computing, 9(28):863–887, 2013. Preliminary version in FOCS 2011. doi:
10.4086/toc.2013.v009a028. doi:10.4086/toc.2013.v009a028. - [12]Björn Martinsson. On the NP-Hardness Approximation Curve for Max-2Lin(2). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), pages 11:1–11:38, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2024. doi:
10.4230/LIPIcs.APPROX/RANDOM.2024.11. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.11. - [13]Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise Stability of Functions with Low Influences: Invariance and Optimality. Annals of Mathematics, 171(1):295–341, 2010. doi:
10.4007/annals.2010.171.295. doi:10.4007/annals.2010.171.295. - [14]Ran Raz. A Parallel Repetition Theorem. SIAM Journal on Computing, 27(3):763–803, 1998. doi:
10.1137/S0097539795280895. doi:10.1137/S0097539795280895. - [15]Mårten Wiman. Improved Inapproximability of Max-Cut through Min-Cut. Master's thesis, KTH Royal Institute of Technology, 2018. University repository full text.