The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance 1/2-ε and rate Ω(ε2) (where an upper bound of O(ε2log(1/ε)) is known). Ta-Shma [STOC 2017] gave an explicit construction of ε-balanced binary codes, where any two distinct codewords are at a distance between 1/2-ε/2 and 1/2+ε/2, achieving a near optimal rate of Ω(ε2+β), where β→ 0 as ε→ 0. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by Ta-Shma, in the adversarial error model. We prove the following results for ε-balanced codes with block length N and rate Ω(ε2+β) in this family: -For all , there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time NOε,β(1). -For any fixed constant β independent of ε, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time (log(1/ε))O(1)·NOβ(1). -For any , there are explicit ε-balanced codes with rate Ω(ε2+β) which can be list decoded up to error 1/2-ε'in time NOε,ε',β(1), where ε',β→ 0 as ε→ 0. The starting point of our algorithms is the framework for list decoding direct-sum codes develop in Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in ε. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shma's construction.

We consider families of codes obtained by “lifting” a base code through operations such as k-XOR applied to “local views” of codewords of , according to a suitable k-uniform hypergraph. The k-XOR operation yields the direct sum encoding used in works of [Ta-Shma, STOC 2017] and [Dinur and Kaufman, FOCS 2017]. We give a general framework for list decoding such lifted codes, as long as the base code admits a unique decoding algorithm, and the hypergraph used for lifting satisfies certain expansion properties. We show that these properties are indeed satisfied by the collection of length k walks on a sufficiently strong expanding graph, and by hypergraphs corresponding to high-dimensional expanders. Instantiating our framework, we obtain list decoding algorithms for direct sum liftings corresponding to the above hypergraph families. Using known connections between direct sum and direct product, we also recover (and strengthen) the recent results of Dinur et al. [SODA 2019] on list decoding for direct product liftings. Our framework relies on relaxations given by the Sum-of-Squares (SOS) SDP hierarchy for solving various constraint satisfaction problems (CSPs). We view the problem of recovering the closest codeword to a given (possibly corrupted) word, as finding the optimal solution to an instance of a CSP. Constraints in the instance correspond to edges of the lifting hypergraph, and the solutions are restricted to lie in the base code . We show that recent algorithms for (approximately) solving CSPs on certain expanding hypergraphs by some of the authors also yield a decoding algorithm for such lifted codes. We extend the framework to list decoding, by requiring the SOS solution to minimize a convex proxy for negative entropy. We show that this ensures a covering property for the SOS solution, and the “condition and round” approach used in several SOS algorithms can then be used to recover the required list of codewords.