lemmaroutine

Completeness of the latent matrix test

A 1−ξ1-\xi assignment gives the matrix game value ≥ 1−kξ−p∗/21-k\xi-p_*/2
completeness half of the matrix-game gap
Lemma·lem:outer-completeness·§4.4 The latent matrix test and completeness

Statement (paper)

If E\mathcal E has an assignment of value at least 1−ξ1-\xi, and the latent map satisfies Pr⁡x uniform in V, a∼μ[C(x+a)≠C(x)]≤p∗, \Pr_{x\text{ uniform in }\mathcal V,\ a\sim\mu} [C(x+a)\ne C(x)]\le p_*, then val⁡(G)≥1−kξ−p∗2. \val(\mathcal G)\ge 1-k\xi-\frac{p_*}{2}.

In plain English

If the instance E\mathcal E has an assignment of value at least 1−ξ1-\xi, and the latent map CC satisfies Pr⁡x, a∼μ[C(x+a)≠C(x)]≤p∗\Pr_{x,\,a\sim\mu}[C(x+a)\ne C(x)]\le p_*, then the matrix game G\mathcal G has value at least 1−kξ−p∗/21-k\xi-p_*/2.

Why it's here

This is the completeness half of the matrix gap: a good assignment for E\mathcal E yields a strategy for G\mathcal G whose loss is a kξk\xi term from the kk constraints it checks plus a p∗/2p_*/2 term from the latent map failing to be invariant under the shift aa. Proposition 6.3 uses it to make completeness adjustable through the choice of p∗p_* while the soundness gap stays fixed.
Classified routine:
A standard completeness calculation for a composed test: a union bound over the k checked constraints gives the k·ξ loss, and the failure of the latent map to be shift-invariant gives the p_*/2 term, in the style of usual Unique Games / 2-to-2 completeness arguments.

Uses

Nothing else in the paper

Used by

propMatrix game completeness and soundness gap

Sources

PaperOpen
Section
§4.4 The latent matrix test and completeness
Page
—
Label
lem:outer-completeness
Line
sections/03-game.tex:319
Leannot aligned

Phase 2 aligns this node to a Lean declaration.