diff f6bf760..6fbd3ac min_uncut_hardness_v2.txt
diff --git a/min_uncut_hardness_v2.txt b/min_uncut_hardness_v2.txt
index 90bed8f..54e847b 100644
--- a/min_uncut_hardness_v2.txt
+++ b/min_uncut_hardness_v2.txt
@@ -3,7 +3,7 @@ For a finite undirected graph G = (V,E) and a subset S of V, uncut_G(S) counts e
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: ./pdf/acmm-2005.pdf
-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.
+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 ineuality 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?: ./pdf/kkmo-2007.pdf
Hastad, Huang, Manokaran, ODonnell, Wright 2017, Improved NP-inapproximability for 2-variable linear equations: ./pdf/hhmow-2017.pdf
Wiman 2018, Improved inapproximability of Max-Cut through Min-Cut: ./pdf/wiman-2018.pdf
@@ -19,7 +19,7 @@ For the randomized form, the given approximation returns S with the C-bound with
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.
+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; uneual 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.
@@ -51,7 +51,7 @@ Define the smoothed field F_B from R^X to R by F_B(c) = E_{g, lambda} f(P_{c + s
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: ./pdf/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,
+Bessel ineuality 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).
@@ -83,9 +83,9 @@ holds for every nonzero frequency, where k denotes the same codeword and x is an
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.
+Box Cauchy-Schwarz. For any real array v: Y -> R and any face multipliers a_j: Y_{-j} -> [-1, 1], the iterated Cauchy-Schwarz ineuality 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 ineuality is the standard iterated Cauchy-Schwarz bound from hypergraph regularity theory.
Gowers 2007, Hypergraph regularity and the multidimensional Szemeredi theorem: ./pdf/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
+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 ineualities
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.
@@ -110,7 +110,7 @@ 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
+The clipped fields w^0, w^{ij} satisfy |w| <= A_0 pointwise and ||w||_2 <= H. Applying the box Cauchy-Schwarz ineuality 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|,
@@ -163,12 +163,12 @@ Composition. A pair of folded bit proofs (f_U on A_U and f_V on A_V) is compared
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
+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 ineuality 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.
+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 ineuality 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.
@@ -187,7 +187,7 @@ Every parameter depends only on J and K, not on phi. The alphabets A_xi and the
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.
+Each choice is fixed by an ineuality 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.
@@ -199,7 +199,7 @@ Exact sign classification. Every threshold input has the form a + b sqrt(N) with
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. Write b_j = s_j/t_j in lowest terms and set D_0 = Q M_b, where Q is the cell-mass denominator and M_b a common multiple of the s_j, so every elementary weight mu_hat(o)/b_j times D_0 is an integer; the graph optimum then equals D_0 times the rational-model 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.
+Path realisation of integer costs. Write b_j = s_j/t_j in lowest terms and set D_0 = Q M_b, where Q is the cell-mass denominator and M_b a common multiple of the s_j, so every elementary weight mu_hat(o)/b_j times D_0 is an integer; the graph optimum then equals D_0 times the rational-model cost. For each comparison entry (a uniform equality or ineuality demand between two label variables) take a fresh path of length four (equality) or three (ineuality) 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.