Smooth LTC Has Cayley Spectral And Metric Characterizations

Claim/Theorem

Let \(C\) be an \(\mathbb F_2\)-linear code of blocklength \(n\), dimension \(k\), and distance \(d\).

Then the following are equivalent:

1. \(C\) has an \(\varepsilon\)-smooth local tester of soundness \(\delta\).

2. There exists a Cayley graph

   \[ \mathcal G=\operatorname{Cay}(\mathbb F_2^h,\mathcal D) \]

   and a set \(S=\{b_1,\dots,b_n\}\) of linear maps \(b_i:\mathbb F_2^h\to\mathbb F_2\) such that

   \[ h=n-k, \]

   \(S\) is \(d\)-wise linearly independent,

   \[ \lambda(b_i)\ge 1-2\varepsilon \qquad \text{for all }i, \]

   and

   \[ \lambda(b)\le 1-2\delta\,\operatorname{rk}_S(b) \qquad \text{for every linear map }b:\mathbb F_2^h\to\mathbb F_2, \]

   where \(\operatorname{rk}_S(b)\) is the minimum size of a subset \(T\subseteq S\) with \(b=\sum_{i\in T} b_i\).

In the asymptotically good strong-soundness regime, this further specializes to the metric statement:

• there is an asymptotically good smooth LTC with \(\varepsilon/\delta=O(1)\) if and only if there is a Cayley graph

  \[ \mathcal G=\operatorname{Cay}(\mathbb F_2^h,S) \]

  with

  \[ |S|=(1+\Omega(1))h, \]

  \(S\) \(\Omega(h)\)-wise linearly independent, and shortest-path metric embedding into \(\ell_1\) with distortion \(O(1)\).

So smooth LTC is exactly a Cayley-graph phenomenon with equivalent spectral and metric formulations.

Dependencies

• None.

Conflicts/Gaps

• This node gives an equivalence, not a stronger structural hypothesis than smooth LTC itself.
• It therefore does not by itself identify the extra irreducibility needed for the balanced-cut connectivity frontier in Conjecture 3.
• Combined with [[good-ltc-does-not-imply-balanced-cut-rank.md]], it shows that neither the Cayley, spectral, nor metric reformulation of LTC by itself can settle the current cut-rank problem.

Sources

• 10.1145/2554797.2554807