claimroutine

Coarse completeness in independent neighbor experiment

Strong labeling gives payoff ≥

(1-\zeta)(1-2\kappa)^k v_{\rm loc}

completeness in the independent-neighbor experiment

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

Statement (paper)

If a labeling

L

strongly satisfies at least

(1-\zeta)|A|

left vertices, then the coarse rank map

f(b,z)=z_{L(b)}

satisfies

V(f)\ge (1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}

, where

V(f)=\mathbb E\,\overline{P_0}(f(w_1),\ldots,f(w_k))

is taken over the independent neighbor experiment with raw output positions

w_i=(b_i,\pi_{a\to b_i}\widetilde Z_i)

In plain English

If a labeling

L

strongly satisfies at least

(1-\zeta)|A|

left vertices, then the coarse rank map

f(b,z)=z_{L(b)}

achieves expected payoff

V(f)\ge(1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}

in the independent neighbor experiment.

Why it's here

This is the completeness half of the finite ordering transfer: a good Unique Games labeling yields a rank assignment whose value is close to the local value

v_{\mathrm{loc}}\ge1-\eta

from the local instance. The loss factors reflect left vertices that are not strongly satisfied (the

1-\zeta

) and the noise perturbation of the

k

sampled coordinates (the

(1-2\kappa)^k

). The later claim that conditions on distinct neighbors uses this lower bound to obtain the strict gap.

Classified routine:

This is the standard completeness analysis of a Khot–Kindler–Mossel–O'Donnell style dictatorship-test reduction from Unique Games: a dictator (long-code) encoding of a good labeling reads off the correct coordinate unless noise hits it. It is a direct calculation from the local instance's value.

Uses

lemFinite local ordering instance with Gram datalemLow-influence functions cannot beat opt_q(J)

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:655

Leannot aligned

Phase 2 aligns this node to a Lean declaration.