claimroutineinferred_dep

Conditioning on distinct neighbors gives strict gap

Conditioning on distinct neighbors changes values by at most δh\delta_h
makes constraints strict, carrying both bounds
Claim·§A.2 The finite ordering transfer·inside propFinite ordering transfer from Unique Games

Statement (paper)

Let DD be the event that b1,…,bkb_1,\ldots,b_k are distinct, and let pD=Pr⁡(D)=(h)k/hkp_D=\Pr(D)=(h)_k/h^k and δh=1−pD≤(k2)/h\delta_h=1-p_D\le\binom{k}{2}/h for h≥kh\ge k. Let I0I_0 be the finite weighted distribution of strict P0P_0 constraints obtained by conditioning on DD, with all output IDs distinct. Then YES: OPT⁡P0(I0)≥(1−ζ)(1−2κ)kvloc−δh\mathrm{YES}:\ \OPT_{P_0}(I_0)\ge(1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}-\delta_h, and NO: OPT⁡P0(I0)≤Sloc+χ+δh\mathrm{NO}:\ \OPT_{P_0}(I_0)\le S_{\mathrm{loc}}+\chi+\delta_h whenever ν<χκt4/6400\nu<\chi\kappa t^4/6400. After applying , the emitted instance II uses the original predicate Π\Pi with exactly the same values as I0I_0.

In plain English

Conditioning the neighbor experiment on the kk sampled neighbors b1,…,bkb_1,\ldots,b_k being distinct (an event of probability 1−δh1-\delta_h with δh≤(k2)/h\delta_h\le\binom{k}{2}/h) yields a strict P0P_0-constraint instance I0I_0 with distinct variables. Its optimum is at least (1−ζ)(1−2κ)kvloc−δh(1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}-\delta_h in the YES case and at most Sloc+χ+δhS_{\mathrm{loc}}+\chi+\delta_h in the NO case when ν<χκt4/6400\nu<\chi\kappa t^4/6400; after the slot permutation the emitted instance with predicate Π\Pi has the same values.

Why it's here

This transfers the completeness bound (claim 1) and the soundness bound (claim 5), both proved for the independent neighbor experiment, to the conditioned distribution. Conditioning on distinct neighbors changes the value by at most δh\delta_h, since the conditioning event fails with probability only δh\delta_h. This makes the constraints strict on distinct variables, and the result feeds the final parameter choice giving the ordering gap.
Classified routine:
A direct consequence of claims 1 and 5: conditioning on the distinct-neighbors event, whose failure probability is bounded by a birthday/union bound (k2)/h\binom{k}{2}/h, moves the value by at most δh\delta_h. This is standard bookkeeping that carries over the completeness and soundness bounds from the independent neighbor experiment.

Uses

claimCoarse completeness in independent neighbor experimentclaimNonpseudorandom excess decodes to game labeling

Used by

claimParameter choices give final ordering gapclaimExplicit rational encoding is polynomial

Sources

PaperOpen
Section
§A.2 The finite ordering transfer
Page
—
Label
—
Line
appendices/finite-consequences.tex:852
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Conditioning on distinct neighbors gives strict gap" rests on claim-prop-finite-ordering-transfer-1
  • info
    inferred_dep
    outline: "Conditioning on distinct neighbors gives strict gap" rests on claim-prop-finite-ordering-transfer-5