claimroutineinferred_dep

Parameter choices give final ordering gap

Parameters give OPTΠ>1−δ\mathrm{OPT}_\Pi>1-\delta if YES and <ρΠ+δ<\rho_\Pi+\delta if NO
closes the proof with the final gap
Claim·§A.2 The finite ordering transfer·inside propFinite ordering transfer from Unique Games

Statement (paper)

With the parameters η,κ,q,J,m,α,t,χ,ζ,ν,H\eta,\kappa,q,J,m,\alpha,t,\chi,\zeta,\nu,H chosen as above (depending only on k,Π,δk,\Pi,\delta), for every h≥Hh\ge H and every R≥1R\ge1 one has δh<η\delta_h<\eta, and the emitted instance II satisfies: in the YES case OPT⁡Π(I)≥1−ζ−2κk−η−δh>1−4η>1−δ\OPT_\Pi(I)\ge 1-\zeta-2\kappa k-\eta-\delta_h>1-4\eta>1-\delta, and in the NO case OPT⁡Π(I)≤Sloc+χ+δh<ρΠ+6η<ρΠ+δ\OPT_\Pi(I)\le S_{\mathrm{loc}}+\chi+\delta_h<\rho_\Pi+6\eta<\rho_\Pi+\delta.

In plain English

With the parameters η,κ,q,J,m,α,t,χ,ζ,ν,H\eta,\kappa,q,J,m,\alpha,t,\chi,\zeta,\nu,H fixed in terms of k,Π,δk,\Pi,\delta, every h≥Hh\ge H and R≥1R\ge1 give δh<η\delta_h<\eta. The emitted instance II then has OPT⁡Π(I)>1−δ\OPT_\Pi(I)>1-\delta in the YES case and OPT⁡Π(I)<ρΠ+δ\OPT_\Pi(I)<\rho_\Pi+\delta in the NO case.

Why it's here

This closes the proof of the proposition: the parameters are chosen so that the conditioned YES and NO bounds from the previous claim turn into the gap 1−δ1-\delta versus ρΠ+δ\rho_\Pi+\delta. Taking HH large makes the distinctness error δh≤(k2)/h\delta_h\le\binom{k}{2}/h smaller than η\eta. The remaining losses (ζ\zeta, 2κk2\kappa k, χ\chi, and the gaps between vlocv_{\mathrm{loc}}, SlocS_{\mathrm{loc}} and 11, ρΠ\rho_\Pi) are each a small multiple of η\eta, and the constants do not depend on RR or hh.
Classified routine:
Parameter bookkeeping that combines the conditioned YES/NO bounds of the previous claim with the distinctness bound δh≤(k2)/h\delta_h\le\binom{k}{2}/h. It chooses HH large and every loss a small multiple of η\eta, in the usual style of Raghavendra/Guruswami et al. ordering-CSP reductions.

Uses

lemFinite local ordering instance with Gram datalemUnique Games with constant left degree and strong satisfactionthmThe Unique Games TheoremlemLow-influence functions rarely collide under couplinglemLow-influence functions cannot beat opt_q(J)claimConditioning on distinct neighbors gives strict gap

Used by

Nothing in the paper

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Parameter choices give final ordering gap" rests on lem:ordering-collision
  • info
    inferred_dep
    outline: "Parameter choices give final ordering gap" rests on lem:ordering-rounding
  • info
    inferred_dep
    outline: "Parameter choices give final ordering gap" rests on claim-prop-finite-ordering-transfer-6