Strong LTC Constraint Graph Is A Small-Set Expander¶

Claim/Theorem¶

Let \(C\subseteq\{0,1\}^n\) be a \(\rho\)-strong LTC of relative distance \(\Delta\), and let \(G=(V,E)\) be its associated constraint graph with average degree

\[ d=\frac{|E|}{|V|}. \]

Then \(G\) is a

\[ \left(\frac{d\rho}{3},\frac{3\Delta}{4}\right) \]

small-set expander: every vertex set \(S\subseteq V\) with

\[ |S|\le \frac{3\Delta n}{4} \]

satisfies

\[ E(S,V\setminus S)\ge \frac{d\rho}{3}|S|. \]

Moreover, \(V\) can be partitioned into at most \(2/\Delta\) large parts

\[ V=S_1\sqcup\cdots\sqcup S_t \]

such that each induced graph \(G[S_i]\) is an expander and the code is approximately a product of approximately locally testable subcodes on the parts.

This gives a necessary irreducibility condition for strong LTCs: a sparse tester cannot have a genuinely sparse cut on any set up to linear size unless the code approximately decomposes along that cut.

Dependencies¶

[[ltc-sparse-cut-product-decomposition.md]]

Conflicts/Gaps¶

The expansion lives in the constraint graph of a chosen tester, not in the intrinsic code connectivity function \(\lambda_C(L)\) or stabilizer cut rank \(\chi_L(\mathcal S)\).
The theorem is for strong LTCs. The weak-LTC version is softer and does not directly give the same small-set expansion statement.
The node gives a necessary condition for tester structure, but not yet a lower bound on syndrome-extraction depth or on balanced cut rank.

Sources¶

dinurLocallyTestableCodes