claimroutine

Few influential coordinates per right vertex

Each right vertex has at most

3200/(\kappa t^3)

influential coordinates

gives

R

-independent candidate label lists

Claim·§A.2 The finite ordering transfer·inside propFinite ordering transfer from Unique Games

Statement (paper)

For every

b\in B

, the set

\mathcal L_b

of coordinates

\ell\in[R]

such that

\operatorname{Inf}_\ell\bigl(T_{1-\kappa}\mathbf1_{\{o_b(z)\in I\}}\bigr)>t/2

for some rank interval

I

satisfies

|\mathcal L_b|\le \frac{400}{\kappa(t/2)^3}=\frac{3200}{\kappa t^3}

, a bound uniform in

R

In plain English

For each right vertex

b\in B

, the set

\mathcal L_b

of coordinates

\ell\in[R]

where

T_{1-\kappa}\mathbf1_{\{o_b(z)\in I\}}

has influence above

t/2

for some rank interval

I

has size at most

\frac{3200}{\kappa t^3}

, independent of

R

Why it's here

This is the standard bound that a noise-smoothed function has few influential coordinates, applied to the indicator functions of rank intervals. It gives a list of candidate labels for each right vertex whose size does not depend on

R

. That list is what lets the next claim decode a nonpseudorandom excess into a labeling of the game

\Phi

with value above

\nu

, which is a contradiction when

\val(\Phi)\le\nu

Classified routine:

Applies the standard fact that a noise-smoothed bounded function has total influence O(1/κ), so only O(1/(κτ)) coordinates exceed influence τ (as in Khot–Kindler–Mossel–O'Donnell 2007). Here it is combined with a union bound over the O(1/t) rank intervals.

Uses

Nothing else in the paper

Used by

claimNonpseudorandom excess decodes to game labeling

Sources

PaperOpen

Section: §A.2 The finite ordering transfer
Page: —
Label: —
Line: appendices/finite-consequences.tex:785

Leannot aligned

Phase 2 aligns this node to a Lean declaration.