theoremstandardstructure_uncertain

Gap hardness for weighted parity equations

Reduces SAT to weighted parity equations with gap 1−ξ1-\xi vs 1/2+ξ1/2+\xi
starting hardness gap for the whole reduction
Theorem·thm:parity·§4.1 Weighted parity equations and distinct positions

Statement (paper)

For every fixed rational ξ>0\xi>0, there is a deterministic polynomial-time reduction from Boolean satisfiability to weighted parity instances, with binary-encoded rational weights, such that YES:OPT⁡(E)≥1−ξ,NO:OPT⁡(E)≤12+ξ. \begin{array}{ll} \textup{YES:}&\OPT(\mathcal E)\ge 1-\xi,\\ \textup{NO:}&\OPT(\mathcal E)\le \frac12+\xi. \end{array} The running-time polynomial may depend on ξ\xi.

In plain English

For every fixed rational ξ>0\xi>0, satisfiability reduces in deterministic polynomial time to weighted parity-equation instances E\mathcal E with binary-encoded rational weights. Satisfiable inputs give OPT⁡(E)≥1−ξ\OPT(\mathcal E)\ge 1-\xi, and unsatisfiable inputs give OPT⁡(E)≤12+ξ\OPT(\mathcal E)\le \tfrac12+\xi.

Why it's here

This is the starting hardness input for the paper's route to the Unique Games Theorem. It supplies a near-perfect versus near-random gap for parity equations, which later steps convert into a unique game, so the final game's YES and NO values rest on it. The running time may depend on ξ\xi, so ξ\xi must be fixed in advance.
Classified standard:
This is Håstad's optimal inapproximability theorem for Max-3LIN over GF(2) (Håstad 2001, "Some optimal inapproximability results"), which gives (1−ξ, 1/2+ξ) NP-hardness for parity equations. The weighted version is the form commonly used in the literature.

Uses

Nothing else in the paper

Used by

thmThe Unique Games TheoremclaimYES and NO values of the final game

Figures

A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least $\gamma>0$ (Proposition 5.3), while a NO parity instance gives agreement at most $\exp(-ck^{1/3})$ for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large $k$: $\exp(-ck^{1/3})<\gamma$.
Figure 1diagramp. 6
The solid arrows describe the reduction; the dashed arrows describe its soundness argument. The decoding lower bound follows from high test acceptance, while the clean-coordinate upper bound follows from the NO parity gap and applies to every advice strategy. The constants c,γ>0c,\gamma>0 are fixed before the tuple length kk grows.
What it shows
A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least γ>0\gamma>0 (Proposition 5.3), while a NO parity instance gives agreement at most exp⁡(−ck1/3)\exp(-ck^{1/3}) for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large kk: exp⁡(−ck1/3)<γ\exp(-ck^{1/3})<\gamma.
Read from the image by claude-opus-5.5 · confidence 88%
SupportsthmThe Unique Games TheoremlemLatent alphabet gadget with detecting noisepropMatrix test passing yields decoding strategieslemAdvice agreement decays with clean coordinatesthmGap hardness for weighted parity equationsthmParallel repetition for projection gameslemSubdivision yields unweighted simple gamepropMatrix game completeness and soundness gap

Sources

PaperOpen
Section
§4.1 Weighted parity equations and distinct positions
Page
—
Label
thm:parity
Line
sections/03-game.tex:25
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    structure_uncertain
    No proof in paper; imported from Håstad's Theorem 5.4.