claimroutineinferred_dep

Nonpseudorandom excess decodes to game labeling

Excess payoff forces nonpseudorandom vertices, decoding a labeling above ν\nu
global soundness bound for orderings
Claim·§A.2 The finite ordering transfer·inside propFinite ordering transfer from Unique Games

Statement (paper)

If val⁡(Φ)≤ν<χκt46400\val(\Phi)\le\nu<\frac{\chi\kappa t^4}{6400}, then V(O)≤Sloc+χV(O)\le S_{\mathrm{loc}}+\chi for every injective OO. Equivalently, if V(O)>Sloc+χV(O)>S_{\mathrm{loc}}+\chi, then more than a χ\chi fraction of left vertices are nonpseudorandom and some labeling of Φ\Phi has edge value greater than χκt4/6400\chi\kappa t^4/6400.

In plain English

If val⁡(Φ)≤ν<χκt46400\val(\Phi)\le\nu<\frac{\chi\kappa t^4}{6400}, then every injective ordering OO has V(O)≤Sloc+χV(O)\le S_{\mathrm{loc}}+\chi. Equivalently, if V(O)>Sloc+χV(O)>S_{\mathrm{loc}}+\chi, then more than a χ\chi fraction of left vertices are nonpseudorandom and some labeling of Φ\Phi has edge value above χκt4/6400\chi\kappa t^4/6400.

Why it's here

This turns the local bound for pseudorandom vertices into a global bound on the ordering value. Any excess over SlocS_{\mathrm{loc}} must come from nonpseudorandom left vertices. Each of those has a short, RR-independent candidate list of labels from the influential-coordinate bound, and choosing labels from these lists gives a game labeling of value above ν\nu, contradicting val⁡(Φ)≤ν\val(\Phi)\le\nu.
Classified routine:
This is the standard soundness decoding step of UG-hardness reductions (Khot–Kindler–Mossel–O'Donnell style, as in Guruswami–Manokaran–Raghavendra for ordering CSPs). Nonpseudorandom vertices get short lists of influential coordinates, and choosing random labels from these lists yields a labeling whose value contradicts the game's value bound. It follows directly from the two preceding claims.

Uses

claimPseudorandom vertices have local payoff boundclaimFew influential coordinates per right vertex

Used by

claimConditioning on distinct neighbors gives strict gap

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Nonpseudorandom excess decodes to game labeling" rests on claim-prop-finite-ordering-transfer-3
  • info
    inferred_dep
    outline: "Nonpseudorandom excess decodes to game labeling" rests on claim-prop-finite-ordering-transfer-4