Near-linear time decoding of Ta-Shma's codes via splittable regularity

The Gilbert-Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2ε/2 and rate Ω(ε 2 ). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2ε/2 and rate Ω(ε 2+α ), where α → 0 as ε → 0. Moreover, the codes in Ta-Shma's construction are ε-balanced, where the distance between distinct codewords is not only bounded from below by 1/2ε/2, but also from above by 1/2 + ε/2.

Polynomial time decoding algorithms for (a slight modification of) Ta-Shma's codes appeared in [FOCS 2020], and were based on the Sum-of-Squares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form N O α (1) for unique decoding, and N O ε,α (1) for the setting of "gentle list decoding", with large exponents of N even when α is a fixed constant. We derive new algorithms for both these tasks, running in time O ˜ε(N). Our algorithms also apply to the general setting of decoding direct-sum codes.

Our algorithms follow from new structural and algorithmic results for collections of k-tuples (ordered hypergraphs) possesing a "structured expansion" property, which we call splittability. This property was previously identified and used in the analysis of SoS-based decoding and constraint satisfaction algorithms, and is also known to be satisfied by Ta-Shma's code construction. We obtain a new weak regularity decompomposition for (possibly sparse) splittable collections W ⊆ [n] k , similar to the regularity decomposition for dense structures by Frieze and Kannan [FOCS 1996]. These decompositions are also computable in near-linear time O ˜(|W|), and form a key component of our algorithmic results.