theoremstandardunresolved_ref

Inverse shortcode theorem

Shift-invariant ff on matrices is affine Mz+uMz+u on a low-codimension slice
decodes invariant tables into structured advice
Theorem·thm:shortcode·§5.1 The inverse shortcode theorem

Statement (paper)

For every η∈(0,1)\eta\in(0,1) there are α∈(0,1]\alpha\in(0,1], an integer rs≥1r_{\rm s}\ge1, and an integer ℓ0\ell_0, depending only on η\eta, with the following property. For every ℓ≥ℓ0\ell\ge\ell_0 there is m0=m0(η,ℓ)m_0=m_0(\eta,\ell) such that, for every m≥m0m\ge m_0 and every function f:Mat⁡ℓ,m→F2ℓf:\operatorname{Mat}_{\ell,m}\to\F_2^\ell, if Pr⁡M,a,l[f(M)=f(M+al⊤)]≥η, \Pr_{M,a,l}\bigl[f(M)=f(M+a l^\top)\bigr]\ge\eta, then some slice S\mathcal S as in Equation , with nr,nc≤rsn_r,n_c\le r_{\rm s}, and some z∈F2mz\in\F_2^m, u∈F2ℓu\in\F_2^\ell satisfy Pr⁡M∣S[f(M)=Mz+u]≥α. \Pr_{M\mid\mathcal S}[f(M)=Mz+u]\ge\alpha. Here MM, a∈F2ℓa\in\F_2^\ell, and l∈F2ml\in\F_2^m are independent and uniform, and M∣SM\mid\mathcal S is uniform on the slice. No folding condition is imposed on ff.

In plain English

If a map ff from ℓ×m\ell\times m matrices over F2\F_2 to F2ℓ\F_2^\ell satisfies f(M)=f(M+al⊤)f(M)=f(M+al^\top) with probability at least η\eta for random MM and random a,la,l, then on some slice with at most rsr_{\rm s} row and rsr_{\rm s} column constraints, f(M)=Mz+uf(M)=Mz+u for an α\alpha fraction of matrices. Here α\alpha and rsr_{\rm s} depend only on η\eta, and ℓ,m\ell,m must be large enough.

Why it's here

This is the decoding tool that turns invariance of ff under random rank-one perturbations into an affine description Mz+uMz+u on a low-codimension slice. It needs no folding assumption. The proof finds a fiber of ff with good retention, lifts it to the Grassmann setting, and applies the expansion theorem to get a dense row-column slice. Later decoding results use it to extract structured advice from tables that pass the matrix test.
Classified standard:
This is the shortcode/matrix-test soundness result from the 2-to-2 Games line of work. Barak–Kothari–Steurer (2018) reduced it to Grassmann expansion, and Khot–Minzer–Safra (2018) proved that pseudorandom sets in the Grassmann graph have near-perfect expansion. It appears here in a known form, without folding.

Uses

Nothing else in the paper

Used by

thmThe Unique Games TheorempropMatrix test passing yields decoding strategieslemGood row advice is common and gives short answer setsclaimEffective choice of latent and shortcode parametersclaimShortcode contradiction forces large good set

Inside the proof

claimSome fiber has retention at least eta/2claimMatrix chart lift has Grassmann retentionclaimExpansion interval yields row-column slice

Sources

PaperOpen
Section
§5.1 The inverse shortcode theorem
Page
—
Label
thm:shortcode
Line
sections/04-matrix.tex:33
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • warn
    unresolved_ref
    Proof rests on the external Khot–Minzer–Safra Grassmann expansion theorem (cited, not a skeleton statement).