Capacity-Achieving Codes with Inverse-Ackermann-Depth Encoders
This provides the first capacity-achieving codes with simultaneously linear size and extremely shallow (inverse-Ackermann) encoding circuits, addressing a key complexity bottleneck for practical error-correcting codes.
The authors prove existence of error-correcting codes that achieve channel capacity for any additive noise channel over finite fields, with encoders that are linear-size and have depth at most the inverse Ackermann function (≤3 in practice). The construction combines a linear code with a disperser graph, achieving error probability 2^{-Ω(n)} at any rate below capacity.
We prove that for any additive noise channel over $\mathbb{F}_q$, there exist error-correcting codes approaching channel capacity encodable by arithmetic circuits (with weighted addition gates) over $\mathbb{F}_q$ of size $O(n)$ and depth $2α(n)$, where $α(n)$ is a version of the inverse Ackermann function that is at most $3$ for all input lengths $n$ in practice. Our results demonstrate that certain capacity-achieving codes admit highly efficient encoding circuits that are simultaneously of linear size and inverse-Ackermann depth. Our construction composes a linear code with constant rate and relative distance, based on the constructions of Gál, Hansen, Koucký, Pudlák, and Viola [IEEE Trans. Inform. Theory 59(10), 2013] and Drucker and Li [COCOON 2023], with an additional layer formed by a disperser graph. A probabilistic argument over the edge weights of the disperser shows the existence of a deterministic encoder achieving error probability $2^{-Ω(n)}$ at any rate below capacity.