Skip to content

Agreement Expander Lifts Local Testability

Claim/Theorem

Let \(X=(V,T,K,S)\) be a multilayer agreement sampler (MAS) with parameters \((\delta,\lambda,\alpha)\), and let \(C\) be the Tanner code on \(V\) defined by local base codes \(\{C_t\}_{t\in T}\). For each \(s\in S\) and \(k\in K\), let \(C_s\) and \(C_k\) denote the corresponding local lifted codes.

Assume:

  1. for every \(k\in K\), the code \(C_k\) has relative distance \(\delta\);
  2. for every \(s\in S\), the code \(C_s\) is \(\rho\)-locally testable with its natural Tanner tester;
  3. the sampler parameter satisfies
\[ \lambda\le \frac{\rho\delta\alpha}{64}. \]

Then the global lifted code \(C\) is

\[ \frac{\rho\delta\alpha}{16} \]

locally testable with its natural Tanner tester.

The proof is again local-to-global. Starting from a word \(w_0\) that fails a fraction \(\varepsilon\) of the local tests, one:

  1. projects each local view on \(s\in S\) to its nearest codeword in \(C_s\);
  2. uses agreement-expander soundness to stitch those local views into a new global word \(w_1\);
  3. uses the sampler layer to show the failure rate drops from \(\varepsilon\) to at most \(\varepsilon/2\);
  4. iterates logarithmically many times, summing a geometric series of corrections.

So high-dimensional or agreement-expander structure lifts local testability of the local pieces to local testability of the global Tanner code.

Dependencies

  • None.

Conflicts/Gaps

  • This theorem is again about a chosen Tanner representation and its natural tester. It does not speak about intrinsic code connectivity, matroid connectivity, or the stabilizer quantity [[stabilizer-cut-rank-functional.md]].
  • It generalizes the same tester-side local-to-global phenomenon already seen in [[left-right-cayley-ltc-from-local-agreement-plus-expansion.md]], but does not by itself yield puncturing resistance or balanced-cut rank-connectivity.
  • For Conjecture 3, this means the high-dimensional-expander line still needs an additional bridge from agreement structure to intrinsic interface complexity.

Sources

  • 10.48550/arXiv.2005.01045