Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

null (Ed.)The Gilbert–Varshamov bound nonconstructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є2). In a breakthrough result, TaShma [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 TaShma’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) TaShma’s codes appeared in [FOCS 2020], and were based on the SumofSquares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form NOα(1) for unique decoding, and NOє,α(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 Õє(N). Our algorithms also apply to the general setting of decoding directsum codes. Our algorithms follow from new structural and algorithmic results for collections of ktuples (ordered hypergraphs) possessing a “structured expansion” property, which we call splittability. This property was previously identified and used in the analysis of SoSbased decoding and constraint satisfaction algorithms, and is also known to be satisfied by TaShma’s code construction. We obtain a new weak regularity decomposition 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 nearlinear time Õ(W ), and form a key component of our algorithmic results.more » « less

null (Ed.)We construct an explicit and structured family of 3XOR instances which is hard for O(√{log n}) levels of the SumofSquares hierarchy. In contrast to earlier constructions, which involve a random component, our systems are highly structured and can be constructed explicitly in deterministic polynomial time. Our construction is based on the highdimensional expanders devised by Lubotzky, Samuels and Vishne, known as LSV complexes or Ramanujan complexes, and our analysis is based on two notions of expansion for these complexes: cosystolic expansion, and a local isoperimetric inequality due to Gromov. Our construction offers an interesting contrast to the recent work of Alev, Jeronimo and the last author (FOCS 2019). They showed that 3XOR instances in which the variables correspond to vertices in a highdimensional expander are easy to solve. In contrast, in our instances the variables correspond to the edges of the complex.more » « less

null (Ed.)The GilbertVarshamov bound (nonconstructively) establishes the existence of binary codes of distance 1/2ε and rate Ω(ε 2 ) (where an upper bound of O(ε 2 log(1/ε)) is known). TaShma [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 TaShma, 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 N Oε,β(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) ·N Oβ(1) . For any , there are explicit εbalanced codes with rate Ω(ε 2+β ) which can be list decoded up to error 1/2ε ' in time N Oε,ε' ,β(1), where ε ' ,β→ 0 as ε→ 0. The starting point of our algorithms is the framework for list decoding directsum codes develop in Alev et al. [SODA 2020], which uses the SumofSquares 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 TaShma's construction.more » « less