For a finite undirected graph G = (V,E) and a subset S of V, uncut_G(S) counts edges with both endpoints in S or both endpoints outside S, that is, edges not crossing the cut between S and its complement. Set OPT_uncut(G) equal to the minimum of uncut_G(S) over all 2^|V| subsets. Both parts of a partition may be empty; only the edge count appears in the objective. Then OPT_uncut(G) is the smallest number of edges whose deletion leaves a bipartite spanning subgraph. Deleting the uncut edges of any minimizing S leaves G bipartite with bipartition (S, V minus S). Conversely, if an edge set D is deleted so that G minus D is bipartite, the proper two-coloring of G minus D yields a subset S with every edge of D uncut, so uncut_G(S) <= |D|. Taking minima on both sides identifies OPT_uncut(G) with the minimum edge-deletion-to-bipartite number.

Deciding whether OPT_uncut(G) equals zero is two-coloring, hence in P. Computing OPT_uncut exactly is NP-hard, by reduction from Max-Cut. A randomized polynomial-time algorithm attains factor O((log |V|)^(1/2)).
Agarwal, Charikar, Makarychev, Makarychev 2005, O(sqrt(log n)) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems: https://doi.org/10.1145/1060590.1060675

Four sources bound the achievable constant factor. Under the Unique Games Conjecture, the near-satisfiable Max-Cut gap of Khot, Kindler, Mossel, ODonnell yields arbitrarily large constant factors for weighted Min-UnCut. Unconditionally, Hastad, Huang, Manokaran, ODonnell, Wright ruled out every factor below 11/8 for the weighted minimum-deletion form of Max-Cut; Wiman improved to below 1.45685; Martinsson improved to below 73139148/49096883, approximately 1.48969, for the minimum weighted violated two-variable parity-equation problem. Replacing each equality or inequality constraint by a fresh path of length four or three, respectively, transfers that construction to weighted Min-UnCut: with fixed endpoint bits each path has minimum uncut weight zero when the constraint is satisfied and one when it is violated, so absolute cost is preserved up to a common integer denominator.
Khot, Kindler, Mossel, ODonnell 2007, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?: ./kkmo-2007.pdf
Hastad, Huang, Manokaran, ODonnell, Wright 2017, Improved NP-inapproximability for 2-variable linear equations: ./hhmow-2017.pdf
Wiman 2018, Improved inapproximability of Max-Cut through Min-Cut: ./wiman-2018.pdf
Martinsson 2024, On the NP-hardness approximation curve for Max-2Lin(2): https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.11

Theorem. Fix an integer K >= 2. There is a deterministic polynomial-time algorithm sending a 3SAT formula phi to a pair (G, k), where G is a simple finite undirected unweighted graph and k >= 1 is a positive integer coded in binary, such that (i) satisfiable phi gives OPT_uncut(G) <= k, and (ii) unsatisfiable phi gives OPT_uncut(G) > K k. For each fixed K the running time, the number of vertices and edges of G, and the number of bits of k are polynomial in the bit length of phi. Every constant is effective; the algorithm uses no advice, no oracle, no unproved hypothesis.

Corollary 1. For every fixed real C > 1, a deterministic polynomial-time C-approximation of OPT_uncut on simple unweighted graphs implies P = NP. A randomized polynomial-time C-approximation with success probability at least any fixed positive constant places 3SAT in RP.

A deterministic C-approximation returns a partition S with uncut_G(S) <= C OPT_uncut(G). Take the theorem at integer K = max{2, ceil C}. Case (i) forces C OPT_uncut(G) <= C k <= K k, so uncut_G(S) <= K k. Case (ii) forces OPT_uncut(G) > K k, so uncut_G(S) >= OPT_uncut(G) > K k. Comparing uncut_G(S) with the integer K k decides satisfiability without knowledge of OPT_uncut.

For the randomized form, the given approximation returns S with the C-bound with probability at least 1 - epsilon. Compare uncut_G(S) with K k. Any NO instance refuses because uncut_G(S) >= OPT_uncut(G) > K k always. Any YES instance accepts whenever the approximation succeeds, so acceptance probability is at least 1 - epsilon. Three independent repetitions raise the success probability above 1/2, placing 3SAT in RP.

Corollary 2. For every fixed real C > 1, minimum 2CNF clause deletion is NP-hard to approximate within C. A deterministic polynomial-time C-approximation would imply P = NP.

Given G with vertex set V and edge set E, form the 2CNF formula F_G on variables x_v for v in V, with two clauses (x_u OR x_v) and (NOT x_u OR NOT x_v) for each uv in E. For any assignment a, set S_a = {v : a(x_v) = 1}. Equal a-bit at u and v falsifies exactly one of the two clauses; unequal a-bit satisfies both. Hence unsat(F_G, a) equals uncut_G(S_a) for every a. Deleting the clauses falsified by a leaves a formula satisfied by a, so OPT_del(F_G) <= OPT_uncut(G). Conversely, from any feasible deletion set D, an assignment a satisfying F_G minus D falsifies only clauses in D, so unsat(F_G, a) <= |D|; hence OPT_uncut(G) = uncut_G(S_a) <= |D| and OPT_uncut(G) <= OPT_del(F_G). Therefore OPT_del(F_G) = OPT_uncut(G). The map G -> F_G preserves absolute cost, so applying the theorem at K = max{2, ceil C} and comparing a C-approximate deletion size with K k decides 3SAT.

An affine space A over F_2 is a translate of a linear subspace. In coordinates A = F_2^r for r = dim A, so |A| = 2^r. An affine function on A is a map b -> b_0 + sum_{j=1}^r b_j x_j; the affine functions form a vector space D(A) of dimension r+1 over F_2, containing the constant form 1. A frequency of D(A) is a linear form alpha: D(A) -> F_2 with character chi_alpha(b) = (-1)^{alpha(b)}. A real function v on D(A) has Fourier coefficients hat v(alpha) = E_{b in D(A)} v(b) chi_alpha(b), and Parseval says sum_alpha hat v(alpha)^2 = E v^2. The odd frequencies are those satisfying alpha(1) = 1.

For a in A define ev_a: D(A) -> F_2 by ev_a(b) = b(a). Then ev_a is a frequency, ev_a(1) = 1, and a -> ev_a is a bijection from A to the set of odd frequencies. If p: A -> A' is affine, its pullback p^*: D(A') -> D(A) has dual (p^*)^*(ev_a) = ev_{p(a)}. Odd frequencies therefore index hidden labels, and Fourier data at odd frequencies is exactly label data.

A folded bit proof on A is a function f from Boolean tables P: A -> {plus or minus 1} to {plus or minus 1} with f(-P) = -f(P). For a in A the evaluation proof f_a(P) = P(a) is folded. Every test is evaluated against arbitrary folded f. The evaluation encoding is the long code, and the condition f(-P) = -f(P) is the folding symmetry standard in PCP analysis.
Bellare, Goldreich, Sudan 1998, Free bits, PCPs, and nonapproximability: ./bgs-1998.pdf

Fix integers n, m >= 2. Put X = [n]^m and N = |X|. Let R be the set of pairs (i, y) with i in [m] and y in [n]^m having the i-th coordinate deleted. Then |R| = M = m n^{m-1}. A face array B assigns to each row (i, y) an independent uniform affine function B^i_y in D(A), and sets B(x) = sum_{i=1}^m B^i_{x_{-i}} in D(A) for each x in X, with x_{-i} denoting x with coordinate i deleted. Thus B(x)(a) is a bit for each a in A.

The query table uses a standard Gaussian c in R^X, a smoothing parameter sigma > 0, a second standard Gaussian g in R^X, a Gaussian lambda in R^C indexed by codewords, and a second smoothing parameter eta > 0. Put P(z) = sgn(N^{-1/2} sum_{x in X} (c_x + sigma g_x) (-1)^{z_x} + eta lambda_z). The pullback P circ B is the Boolean table on A given by (P circ B)(a) = P(B(a) as a length-|X| bit vector), and its input to f is folded.

Three inner tests perturb one of the three ingredients and check that f is stable.

Test 1 replaces c by c + sigma g + eta lambda and compares f evaluated on the two resulting tables.

Test 2 independently resamples each row B^i_y with probability delta^2 per row and compares f on the two arrays.

Test 3 samples a codeword z in C and forces its entry to +1 in one table and to -1 in another, comparing f on the two required tables.

Write eps_j(f) for the failure probability of Test j under the joint law of (B, c, g, lambda). Let b_1, b_2, b_3, b_4 be positive rational budgets, set by the construction as functions of the parameters sigma, delta, eta, |C|. The folded proof f has cost at most J if eps_j(f) <= J b_j for j = 1, 2, 3 and similarly for the fourth test.

Evaluation proofs. For every a in A the evaluation proof f_a satisfies eps_1 <= 2 sigma, eps_2 <= 2 delta + 2 eta, and eps_3 = |C|^{-1}. The first two bounds follow from the random-hyperplane sign identity of Goemans and Williamson: adding an independent centered Gaussian of standard deviation s to a standard Gaussian changes its sign with probability arctan(s)/pi, which is at most s. Under Test 1 the perturbation has standard deviation (sigma^2 + eta^2)^{1/2} <= 2 sigma; under Test 2 the row-resampling channel preserves the queried bit with probability at least 1 - 2 delta - 2 eta. Under Test 3 exactly one of the |C| codewords matches the query point, giving eps_3 = |C|^{-1}.
Goemans, Williamson 1995, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming: ./gw95.pdf

Set b_1 = 2 sigma, b_2 = 2 delta + 2 eta, b_3 = |C|^{-1}. Evaluation proofs are the cost-1 calibration and every other folded proof pays at least as much, so a NO-case proof must cost more than J.

Define the smoothed field F_B from R^X to R by F_B(c) = E_{g, lambda} f(P_{c + sigma g, eta lambda} circ B), and the gradient field h_x(B, c) = sqrt(N) partial_{c_x} F_B(c). Gaussian integration by parts gives
h_x(B, c) = (sqrt N / sigma) E_{g, lambda} g_x f(P_{c + sigma g, eta lambda} circ B).
The Fourier-Hermite expansion in c and the Gaussian integration-by-parts identity are standard tools of noise stability.
Mossel, ODonnell, Oleszkiewicz 2010, Noise stability of functions with low influences: invariance and optimality: ./moo10.pdf
Bessel inequality for the orthonormal family {g_x}_{x in X} in the joint Gaussian space of (g, lambda) gives, for every B, c and every x in X,
|h_x(B, c)| <= sqrt N / sigma, and E_x |h_x(B, c)|^2 <= sigma^{-2}.

Inner decoding theorem. For every rational J >= 1 there are effectively selectable integers m >= 2 and n >= 2 and positive rationals sigma, delta, eta, p, theta < 1, with eta <= sigma, depending only on J, such that for every finite weighted family of nonempty affine spaces A_xi with folded bit proofs f_xi satisfying eps_j(f_xi) <= J b_j for j = 1, 2, 3, drawing xi, the standard Gaussian c, uniform x in X, uniform i in [m], and all rows of B outside row (i, x_{-i}) independently and uniformly in D(A_xi), the conclusion holds with probability at least p. The function b -> h_x(B[B^i_{x_{-i}} <- b], c) on D(A_xi) has a Fourier coefficient of magnitude at least theta at an odd frequency of D(A_xi).

Define Pi_c as truncation to Hermite degree at most s in c, and Pi_B as truncation to Fourier row degree at most R m in B. Let L_x(B, c) = (Pi_B Pi_c h)_x(B, c). Parseval in the two orthonormal bases makes both projections orthogonal, and the next lemma shows that L retains most of the L^2 energy of h.

Lemma. Suppose eps_j(f) <= J b_j for j = 1, 2, 3. If sigma, delta, eta are small and s, R are large relative to J, then the smoothed field h and its projection L satisfy
E ||h||_{2,x}^2 >= 3/4,
E ||(I - Pi_c) h||_{2,x}^2 <= 1/16,
E ||(I - Pi_B) h||_{2,x}^2 <= 1/32,
E ||L||_{2,x}^2 >= 1/2.

Proof. Set Q_B(u) = E_lambda f(P_{u, eta lambda} circ B). Negating u and changing lambda to -lambda negates every table entry almost surely, and folding gives Q_B(-u) = -Q_B(u). Symmetry of the standard Gaussian under c -> -c gives F_B(-c) = -F_B(c), hence E_c F_B(c) = 0. Jensen with the first test bound gives E |F_B(c) - f_0(B, c)|^2 <= 4 eps_1 <= 4 J b_1, where f_0(B, c) = f(P_{c, 0} circ B) satisfies |f_0| = 1 pointwise. Then ||F_B||_2 >= 1 - (4 eps_1)^{1/2}, so E F_B(c)^2 >= 3/4 when eps_1 <= 1/100. The mean-zero Gaussian energy identity E F_B(c)^2 = sum_x E (partial_{c_x} F_B(c))^2, combined with h_x = sqrt N partial_{c_x} F_B, yields E ||h||_{2,x}^2 = E F_B(c)^2 >= 3/4.

Under Test 1 the added Gaussian noise has variance (sigma^2 + eta^2)/N at each coordinate of the query, and averaging the noise diagonalizes the Hermite expansion by multiplying the coefficient of degree k by (1 - (sigma^2 + eta^2)/N)^{k/2}. Test 1 bounds E ||h(c) - h(c + sigma g + eta lambda)||_{2,x}^2 by sigma^{-2} E |f(c) - f(c + noise)|^2 = 4 eps_1 / sigma^2. If s (sigma^2 + eta^2)/N >= 1, then (1 - (sigma^2 + eta^2)/N)^s <= 1/2, and the degree-beyond-s tail dominates the difference: E ||(I - Pi_c) h||_{2,x}^2 <= 4 * 4 eps_1 / sigma^2 <= 1/16.

Under Test 2 the row-resampling channel independently replaces each row with an independent D(A)-uniform value with probability delta^2. Orthogonality of row characters gives eigenvalue (1 - delta^2)^k on Fourier row degree k. Test 2 bounds E ||h(B) - h(B')||_{2,x}^2 by 4 eps_2 / sigma^2. If R m delta^2 >= 1, then (1 - delta^2)^{R m} <= e^{-1} < 1/2, and the same domination gives E ||(I - Pi_B) h||_{2,x}^2 <= 4 * 4 eps_2 / sigma^2 <= 1/32.

Since Pi_B and Pi_c act on disjoint variables and commute, Parseval gives E ||L||_{2,x}^2 >= 3/4 - 1/16 - 1/32 = 21/32 > 1/2.

The extraction of a large odd coefficient from L proceeds in four steps: identify the low-degree field L with a sum of localised slices, use box Cauchy-Schwarz pairwise across slices to reduce to one-row estimates, and then bootstrap odd Fourier coefficients up to a full row.

Symmetric and regularized reductions. The face code C and face array B are symmetric under two group actions. First, uniformly translating one entire slice of the array preserves B(x) at every x: for fixed distinct axes i, j and tuple q in [n]^[m] minus {i,j}, adding a common a in D(A) to the rows B^i_y with y_{-j} = q and to the rows B^j_{y'} with y'_{-i} = q leaves B(x) unchanged at every x, because the two additions coincide or cancel. Fourier orthogonality therefore forces the cylinder gauge identity
sum_{y: y_{-j} = q} alpha^i_y + sum_{y': y'_{-i} = q} alpha^j_{y'} = 0 in D(A)^* for every nonzero frequency alpha = (alpha^i_y).

Second, adding the codeword k_u = 1_{u_{-i} = v} to a row r = (i, v) of B transforms the underlying Gaussian query table by the affine reparametrization P_{c + sigma g, eta lambda}(z + k) = P_{D_k c + sigma D_k g, eta lambda'}(z), where D_k c = ((-1)^{k_u} c_u) and lambda'_z = lambda_{z + k}. The face array is unchanged as a pointwise function on X, and folding is preserved, so the coefficient identity
alpha_r(1) equivalent k_x + sum_{u in X} k_u I_u mod 2
holds for every nonzero frequency, where k denotes the same codeword and x is any test point of the row.

Localisation. Fix a subbox Y = product_{i=1}^m Y_i of X of side length ell (each Y_i a subset of [n] of size ell containing x_i). The low-degree field L_x depends on B only through rows whose coordinates lie in Y. Write L^{ij}_x for the part of L_x whose Hermite degree has I_x = 0 and whose row-degree distribution loads frequency components on rows B^i_{x_{-i}} and B^j_{x_{-j}} for some fixed pair i < j; write L^0_x for the part whose Hermite degree has I_x >= 1. These parts together account for all of L after fixing pairs (i, j) exhaustively if m is large. For each pair (i, j) and each point x in Y define the slice function V_x on D(A) by summing over frequency components with I_x = 0 and no other on-subbox rows in tables i and j; the equality V_x(b) = sum_{alpha: alpha(1) = 1} hat V_x(alpha) chi_alpha(b) recovers the one-row restriction after averaging over the free local row.

Box Cauchy-Schwarz. For any real array v: Y -> R and any face multipliers a_j: Y_{-j} -> [-1, 1], the iterated Cauchy-Schwarz inequality gives |E_{u in Y} v(u) prod_j a_j(u_{-j})|^{2^m} <= E_{u^0, u^1} prod_{omega in {0,1}^m} v(u^omega), where u^omega is the interleaved point (u_i^{omega_i}). The inequality is the standard iterated Cauchy-Schwarz bound from hypergraph regularity theory.
Gowers 2007, Hypergraph regularity and the multidimensional Szemeredi theorem: ./gowers-2007.pdf
Applying this to v = V and then conditioning on the independent slice functions, the face multipliers drop out and each surviving cube of points has an expected fourth-moment product that can be evaluated with the same row functions on two independent cubes. The pair-correlation inequalities
E d_Y(L^{ij}) <= 2 A_0 (m/ell)^{1/2^m} + sqrt(H (gamma + H^2/A_0)),
E d_Y(L^0)    <= 2 A_0 (m/ell)^{1/2^m},
hold for the clipped-field approximations with A_0 points of clipping, H of L^2 norm, and parameter gamma controlling per-slice Fourier maxima. The first term is small because ell is large compared to m; the second is small by tuning H, A_0, gamma after m, ell, s, R.

For class 0, conditioning on the background Gaussians gives each w^0_x an unconditional mean zero Gaussian dependence, and the box product of class 0 slices bounds the face correlation by the same iterated argument with one factor.

Face correlation. For a real array v on X define d_X(v) = max_{z in C} |N^{-1} sum_{x in X} v_x (-1)^{z_x}|, the largest correlation of v with a codeword character.

First direction. Under eps_j(f) <= J b_j for j = 1, 2, 3 the low-degree field L satisfies E d_X(L) >= 1/(2T) for T = 2 J / eta.

By Gaussian differentiation in the truth-table coordinates of the smoothed field,
h_x(B, c) = sum_{z in C} mu_z(B, c) (-1)^{z_x},
where mu_z(B, c) = eta^{-1} E_{g, lambda} lambda_z f(P_{c + sigma g, eta lambda} circ B). The code characters are orthonormal in the uniform measure on X, so E_x h_x^2 = sum_z mu_z^2. Test 3 bounds E sum_{z in C} |mu_z| from the failure probability of forcing a codeword to a chosen sign; the identity shows E sum |mu_z| <= 2 J / eta = T. Cauchy-Schwarz with the L^1 bound gives
d_X(h) = max_z |mu_z| >= sum_z |mu_z|^2 / sum_z |mu_z| >= E_x h_x^2 / T >= 3/(4T).
The truncation from h to L reduces the right side to >= 1/(2T) because L retains 21/32 of the L^2 energy and the row and Hermite tails have bounded L^1 mass.

Second direction. Suppose, for a contradiction, the inner decoding conclusion fails for some positive p, theta: for every class (i, j) and every x in Y, the event q_x >= theta holds with probability less than p, where q_x is the maximum modulus of the odd Fourier coefficients of the one-row restriction of V_x. Then the class-by-class bounds force E d_X(L) strictly below 1/(2T * (1 + binom(m, 2))).

Process each class. For class 0, the localization and clipping bounds give
E E_{x in Y} |L^0_x - w^0_x| <= e_loc + 2 sigma^{-2}/A_0.
For the class (i, j), the bound is
E E_{x in Y} |L^{ij}_x - w^{ij}_x| <= e_loc + sigma^{-2}/H + e_atom + sigma^{-2}/A_0,
with e_loc = sigma^{-1} sqrt((s + R m) ell / (n - 1)) and e_atom = sigma^{-1} sqrt(C_0/gamma) (theta^2 + m p N / sigma^2)^{1/4}.

The clipped fields w^0, w^{ij} satisfy |w| <= A_0 pointwise and ||w||_2 <= H. Applying the box Cauchy-Schwarz inequality to each class and conditioning on independent cube backgrounds gives
E d_Y(w^0) <= 2 A_0 (m/ell)^{1/2^m},
E d_Y(w^{ij}) <= 2 A_0 (m/ell)^{1/2^m} + sqrt(H(gamma + H^2/A_0)).
Combining with the localization loss through |d_Y(u) - d_Y(v)| <= E_{x in Y} |u_x - v_x|,
E d_X(L^{ij}) <= e_loc + sigma^{-2}/H + e_atom + sigma^{-2}/A_0 + 2 A_0 (m/ell)^{1/2^m} + sqrt(H(gamma + H^2/A_0)),
E d_X(L^0) <= e_loc + 2 sigma^{-2}/A_0 + 2 A_0 (m/ell)^{1/2^m}.

Parameter choice. Fix m large so that (m - s) choose 2 exceeds R m. Choose H -> gamma -> A_0 -> ell -> n -> (p, theta) in that order so that each of the six error terms is below 1/(4 T (1 + binom(m, 2))), and so that theta and p are below the thresholds that make e_atom small while staying positive. Then summing over the 1 + binom(m, 2) classes gives
E d_X(L) <= E d_X(L^0) + sum_{i < j} E d_X(L^{ij}) < 1/(2T).

This contradicts the first direction. The no-odd-coefficient hypothesis must fail: the event q_x >= theta holds with probability at least p at some class with i in [m] and x in Y. By the bijection between odd frequencies and labels, this gives an odd frequency of the one-row restriction of h of magnitude at least theta, which is the conclusion of inner decoding.

From parity to a two-player game. Let E be a uniform list of M_0 parity equations x_{v_1} + x_{v_2} + x_{v_3} = tau in F_2 over variables x_j, with each entry j carrying an equation E^{(j)} that may repeat variable names. Hastad 2001, Theorem 5.4, proves that for every fixed rational zeta > 0 it is NP-hard to distinguish lists in which some assignment satisfies at least (1 - zeta) M_0 equations from lists in which no assignment satisfies more than (1/2 + zeta) M_0 equations. The base game soundness below uses the weaker consequence that for zeta <= 1/4 no assignment satisfies more than 3 M_0 / 4 equations in the NO case.
Hastad 2001, Some optimal inapproximability results: ./hastad-2001.pdf

The list is made uniform by replicating each entry roughly Q times its weight, with Q large enough that satisfaction proportions change by at most epsilon; the NO-case bound persists up to 3/4 + epsilon. All constants are effective in zeta and Q.

The outer game. Fix integers t >= t_0 >= 1. A first question is a tuple U = (E_1, ..., E_t) of t independent uniform list entries. Its label alphabet A_U = product_j A(E_j) is a nonempty affine space of dimension at most 2t (each A(E) is contained in F_2^3). The second question V, given U and a uniform size-t_0 subset H of [t], is a length-t tuple whose coordinate j is a variable question v(E_j, p_j) for a uniform p_j in [3] when j in H, and the full equation E_j when j not in H. Its label alphabet A_V = product_j A_{V,j} with A_{V,j} = F_2 for j in H and A_{V,j} = A(E_j) for j not in H. Acceptance is coordinatewise: the pullback pi_e: A_U -> A_V sends (a_j) to (a_j[p_j])_{j in H} and to a_j for j not in H, and the two labels must agree under pi_e. The use of smooth equation-variable games with affine hints for decoding is standard in the literature.
Khot, Safra 2013, A two-prover one-round game with strong soundness: ./ks13.pdf

Base game soundness. Take t = 1 and H = {1}. The single-coordinate game accepts when the first-player label a at its queried position p equals the second-player bit b. Supposing no assignment satisfies more than 3/4 of the equations, the ordinary game has value at most 11/12.

Fix any deterministic second-player strategy; the bit for each variable name defines a global assignment. On at least 1/4 of the sampled entries this assignment violates the equation, and for every valid first-player answer to such an entry a uniform position p in [3] detects disagreement with probability at least 1/3. So the failure probability is at least (1/4)(1/3) = 1/12, giving value at most 11/12.

Iterated repetition. Raz amplification gives an effective universal constant c < 1 such that the ordinary r-fold repetition of the base game has value at most c^r for every r >= 0.
Raz 1998, A parallel repetition theorem: ./raz-1998.pdf
Holenstein 2009, Parallel repetition: simplifications and the no-signaling case: ./holenstein-2009.pdf

Hint soundness. Suppose both players receive q affine forms L_1, ..., L_q sampled uniformly from D(A_V). The value of the hinted game is at most
(1 - 2^{-q} (1 - c))^{t_0}.
Call a hidden coordinate j in H active if every coefficient beta_{l, j} of z_j in every L_l vanishes. Independence gives |Active| distributed as Binomial(t_0, 2^{-q}) conditional on t_0 and q. For fixed active set, the active coordinates in H are independent of all inactive coordinates and sample fresh equation-position pairs. Restricted to active coordinates the q hints have zero coefficient, so the game value there is at most c^{|Active|}. Averaging over the binomial distribution gives
E c^{|Active|} = (1 - 2^{-q} (1 - c))^{t_0}.
Choosing t_0 large makes this value below any prescribed positive threshold s.
Khot, Minzer, Safra 2017, On independent sets, 2-to-2 games and Grassmann graphs: ./kms17.pdf
Dinur, Khot, Kindler, Minzer, Safra 2025, Towards a proof of the 2-to-1 games conjecture: ./dkkms-2025.pdf

Joint smoothness of pulled-back hints. Beyond soundness of the hinted game, the decoding analysis needs the joint distribution of the pulled-back hints to be close to uniform.

Lemma (joint smoothness). Fix the first question U, integers d >= 1 and t >= t_0 >= 1, and draw the rest of the outer sample conditional on U. Draw d independent uniform affine forms L_1, ..., L_d in D(A_V), sample the outer edge e conditional on U with first side U, and consider the joint distribution of (pi_e^* L_1, ..., pi_e^* L_d) on A_U. Then
TV(Law((pi_e^* L_l)_{l=1}^d | U), Unif(D(A_U)^d)) <= (1/2) sqrt((2^{4 d t_0} - 1) (t_0^2 / t)).
The bound is uniform in U and in the equation list. For fixed (d, t_0) and any positive rational Delta, an effective integer t makes the right side below Delta.

Proof. Write A_j = A(E_j) and r_j = dim A_j <= 2. Choose an affine origin o_j and an injective linear T_j: F_2^{r_j} -> F_2^3 with image the translation space of A_j, so every a_j in A_j has a unique expression a_j = o_j + T_j u_j. For a uniform affine L = kappa + sum_j beta_j in D(A_V), its pullback (pi_e^* L)(a) has constant part kappa and linear part split into two kinds of terms: for j not in H the linear coefficients in beta_j survive intact on A_j; for j in H the pullback only uses one coordinate of A_j, namely the p_j-th, so its linear part collapses to a single uniform bit per (l, j). Distinct hidden indices give independent coin collapses because the p_j are independent uniform in [3].

Conditioning on H and the p_j, the joint law of (pi_e^* L_l)_{l=1}^d is product over j of a block law mu_j with density rho_j against uniform. For j not in H the density is one. For j in H the density is at most 2^{2d}, because there are 2^{r_j d} possible joint linear parts and each has mass at most 2^{-d}. So E rho_j = 1 and 0 <= rho_j <= 2^{2d} uniformly.

Independence across j gives a product density g_H against the uniform product measure on D(A_U)^d, with E g_H = 1 and 0 <= g_H <= 2^{4 d t_0}. The total-variation distance to uniform is at most (1/2) E |g_H - 1|. Writing X = 2^{4 d t_0} and expanding (E g_H)^2 - 1 = 0 in terms of pairwise overlaps between independent subsets H, H', the bound becomes (1/2) sqrt((X - 1) t_0^2 / t). The right side is small when t is large relative to X t_0^2.

Composition. A pair of folded bit proofs (f_U on A_U and f_V on A_V) is compared by four tests: Test 1, 2, 3 applied to f_V alone under the marginal distribution of V, and a fourth test that compares f_U on the pullback of a common table to f_V on the table itself.

Fourth test. Sample a full outer edge e = (U, V, H, p), an independent uniform face array B on D(A_V), and the smoothed Gaussian table P = P_{c + sigma g, eta lambda} on the code C. Compare
f_U(P(pi_e^* B)) with f_V(P(B)).

Row comparison. On the event that the fourth test failure probability is at most J b_4 with b_4 a small budget fixed shortly, the two row-restricted fields h_U and h_V are close in L^2. To make this precise, fix e, B, c and apply the Gaussian differentiation identity to the difference between the two sides. Bessel inequality for the orthonormal functions g_x gives, for the difference between the row functions
H_V(b) = h_{x, V}(B[B^i_{x_{-i}} <- b], c),
H_U(a) = h_{x, U}(pi_e^* B[B^i_{x_{-i}} <- a], c),
the bound
E ||H_V - H_U circ pi_e^*||^2_{L^2(D(A_V))} <= 4 J b_4 / sigma^2
pointwise in x, i, B outside the sampled row, c, and e. Averaging restores a fully independent uniform array via the background. Choosing b_4 a positive rational so that 64 J b_4 / sigma^2 < p/4 lets Markov inequality imply ||H_V - H_U circ pi_e^*|| < theta/4 except on an event of probability below p/4.

Decoder. Fix the sequence of parameters. Suppose for a contradiction that the composed cost is at most J. Then eps_1, eps_2, eps_3 each pass the inner decoding thresholds and eps_4 <= J b_4. Conditional on the common background W (the edge e, the array B outside the chosen row, and the Gaussian c), inner decoding applies to both sides: the first-player list of odd frequencies of H_U of magnitude at least u is a function of W and the first-side information; the second-player list of odd frequencies of H_V of magnitude at least theta is likewise a function of W and the second-side information. On the small complementary event where the row functions are not close within theta/4, the argument still succeeds whenever the event q >= theta holds on both sides.

By Lemma (odd frequencies are labels) each odd frequency corresponds to a unique label in its alphabet. On the event where both lists are nonempty and the row functions are close, the two lists share a common odd frequency beta of H_V of magnitude at least theta; the corresponding pullback alpha = (pi_e^*)^*beta is an odd frequency of H_U of magnitude at least theta minus theta/4 = 3 theta / 4, hence also in the first-player list. Choosing the maximum-magnitude frequency in both lists and letting each player output the label defined by that frequency, the two labels agree under pi_e with probability at least
s_* = (p/2) / ((1 + M_*^2 / u^2) (1 + M_*^2 / theta^2)),
where M_* = M N^{1/2} / sigma is the maximum modulus of any one-row Fourier coefficient.

Parameter contradiction. Fix q = 4 affine hints that the successful decoder implicitly possesses (the pulled-back random affine functions used by the test distributions), and choose t_0 large enough that the hinted-game soundness bound (1 - 2^{-q}(1 - c))^{t_0} is strictly below s_*. Then no collection of proofs has composed cost at most J, because it would output a certain with probability >= s_* at the hinted game while hint soundness says no strategy can do better than s_*.

YES case. Suppose the 3LIN list admits an assignment a satisfying at least 1 - zeta of the equations. On the YES side populate f_U and f_V with the evaluation proofs of the natural labels: give f_U(a_j) = evaluation at a_j inside A_U, and f_V(b_j) = evaluation at b_j inside A_V, where a_j is the honest local solution for the j-th equation and b_j is the honest bit or local solution. Choose any local label in A_j when the equation is violated. Under the resulting joint distribution the labels agree under pi_e on every entry of the edge with probability at least 1 - t zeta, and the four test failure probabilities satisfy eps_1 <= b_1, eps_2 <= b_2, eps_3 <= b_3, eps_4 <= b_4 + t zeta. Choosing t zeta <= b_4 gives composed cost at most 4.

Bit-gap proposition. Fix an integer K >= 2, set J = 10 K. There exist effectively selectable inner parameters (m, n, sigma, delta, eta, p, theta, s, R, H, gamma, A_0, ell), outer parameters (t, t_0, zeta), composition budget b_4, and positive rational budgets b_1, b_2, b_3 such that for every 3SAT formula phi there is a finite weighted family {A_xi}_{xi in Xi} of nonempty affine spaces over F_2, a four-family of folded-bit-proof comparison tests against this family, and a cost function Cost(f) = sum_{j=1}^4 (failure probability of Test j)/b_j, with
(i) if phi is satisfiable, a folded proof family with Cost <= 4 exists;
(ii) if phi is unsatisfiable, every folded proof family has Cost > J.
Every parameter depends only on J and K, not on phi. The alphabets A_xi and the weights are finite in number, with total size poly(|phi|) and constants depending only on K. The two cost bounds are exactly the YES and NO cases.

Parameter order for the construction is
J -> (inner: m, n, sigma, delta, eta, s, R, p, theta) -> (u, Delta, b_4, s_*) -> t_0 -> t -> zeta.
Each choice is fixed by an inequality on the earlier parameters, with rational slack; no real-number oracle is involved. Every constant is effective.

Finite reduction. The comparison system uses continuous Gaussian randomness. Three conversions are required: rational replacement of the sign tables, integral scaling, and realisation of each weighted comparison by an unweighted graph path.

Rational sign tables. Each test depends only on the sign table sgn(t_z) at finitely many codewords z, where t_z = N^{-1/2} sum_x (c_x + sigma g_x)(-1)^{z_x} + eta lambda_z. Replace the Gaussian joint law by a rational discrete approximation mu_hat supported on a grid. Choose T_G >= 1 integer with d/T_G^2 < eps/4 (d = |X|) so that the tail mass of the standard Gaussian outside [-T_G, T_G]^d is below eps/4; the tail bound follows from second-moment estimates in each coordinate and a union bound.

Taylor substitute for the density. Set U = T_G^2/2 and choose an integer r >= 0 such that e_r = U^{2r+1}/(2r+1)! satisfies 2 d T_G e_r < eps/4. Define the rational polynomial Q_r(v) = sum_{j=0}^{2r} (-1)^j v^{2j} / (2^j j!). Taylor remainder gives 0 <= Q_r(v) - e^{-v^2/2} <= e_r on [-T_G, T_G] and Q_r > 0 in the open interval. Partition [-T_G, T_G] into L intervals with rational midpoints, and set the cell mass w_I = int_I Q_r / int_{[-T_G, T_G]} Q_r, computed by rational polynomial antiderivative. The resulting grid distribution has total-variation distance at most 2 d T_G e_r < eps/4 from the rounded conditioned Gaussian law.

Exact sign classification. Every threshold input has the form a + b sqrt(N) with a, b in Q (a T_0 input is a rational; a T_1 input is multiplied by sqrt(N) > 0). If a, b have the same sign or one is zero, the sign is immediate. If a, b have opposite signs, compare the rationals a^2 and N b^2: the term of larger magnitude determines the sign, and equality gives an exact zero. Declare the sign of zero as +1.

Common denominator. Choose a common denominator Q_1 for the finitely many rational cell masses, put Q = Q_1^d, and enumerate the L^d cells. The cell probabilities are integer multiples of 1/Q. Summing numerators over cells with the same sign-table pair produces an explicit rational law mu_hat for the joint sign table. The test failure probabilities for each folded proof against mu_hat versus the original Gaussian law differ by at most 1/(8(1 + W)), where W = sum_j 1/b_j, and the total cost changes by at most 1/2.

Path realisation of integer costs. Multiply each composed cost by 2Q to obtain a common-denominator integer cost. For each comparison entry (a uniform equality or inequality demand between two label variables) take a fresh path of length four (equality) or three (inequality) between the two endpoints, with all internal vertices fresh. For fixed signs of the endpoints, the path minimum uncut cost is zero when the demanded relation holds and one when it is violated, by the alternation argument: writing the signs along the path as x_0, ..., x_L and the uncut edges as r, exactly L - r adjacent pairs have opposite signs, so x_0 x_L = (-1)^{L - r}, and the prescribed relation fixes x_0 x_L.

The reductions composing phi -> 3LIN -> comparison system -> integer demand -> graph G are all deterministic and polynomial in |phi| when K is fixed, encoded in binary. Time, vertices, edges, and number of bits of the resulting integer k are polynomial with constants depending only on K.

Assembly. Fix C > 1, choose an integer K >= max{2, ceil C}, and put J = 10 K. Apply the bit-gap proposition with J at the fixed uniform 3LIN list from phi. The graph G has OPT_uncut(G) <= D_0 in the YES case and OPT_uncut(G) > K D_0 in the NO case, with k = D_0 = 4 Q times a fixed integer scaling factor. A deterministic C-approximation returns a partition S with uncut_G(S) <= C OPT_uncut(G), and comparison of uncut_G(S) with K k decides satisfiability. A randomized C-approximation with success probability at least a fixed positive constant places 3SAT in RP after three independent repetitions.

This completes the reduction from 3SAT to Min-UnCut at every prescribed constant factor.