Two-sided product expanding codes exist with random rademacher matrices
Two-Sided Product Expanding Codes via Rademacher Matrices
Information TheoryComputational ComplexityDiscrete Mathematics
Summary
This paper deals with special kinds of error-correcting codes called two-sided product expanding codes, which help protect information from errors. The authors show these codes exist by using random matrices with simple ±1 entries instead of relying on complicated earlier constructions. They translate the problem into one over real numbers and use advanced math tools to prove their result. This new approach could lead to better ways of building error-correcting codes with symmetries or for more complex structures.
What this means in practice
- •For coding engineers: Design and analyze error-correcting codes with desired expansion properties using random linear codes over large prime fields instead of explicit LTCs.
- •For quantum computing hardware teams: Explore code constructions with symmetries for quantum error correction on complex structures like simplicial complexes enabled by new proof techniques.
A theory result. No direct application yet.
Authors
Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner
Abstract
We give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of Kalachev and Panteleev (FOCS, 2025), does not rely on explicit constructions of asymptotically optimal locally testable codes ($c^3$-LTCs). For every fixed number of component codes and dimensions whose rates are bounded away from zero and one, we show that independent random linear codes over a sufficiently large prime field have constant two-sided product expansion with probability tending to one. The tradeoff is that our proof requires the characteristic to grow with the block length, while [KP25] takes extensions of $\mathbb{F}_2$. To replace the use of $c^3$-LTCs, we develop several new techniques that we view as interesting in their own right. Instead of working directly over finite fields, we work over the reals and use random Rademacher matrices for the generator matrices of the component codes. From here, we we show that the extendability of $\varepsilon$-closed sets can be reduced to controlling the operator norm of sparse restrictions of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner words from Anderson and Zeitouni (Probab. Theory Relat. Fields., 2006), which were originally applied to band matrices. Due to our techniques not relying on explicit $c^3$-LTCs, we believe that they form a promising starting point towards showing the existence of product expanding tensor codes where the component codes have non-trivial automorphism groups and coboundary expanding codes that could be used as the local codes of non-cubical complexes, such as simplicial complexes.