We introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list-decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select $n$ indices of a base code $C\subset \mathbb{F}_q^m$ via an expander random walk on a graph on $[m]$. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires $O(n^2)$ random bits to sample, we sample a pseudorandom linear code with $O(n)$ random bits. We show that pseudorandom puncturings satisfy several desirable properties exhibited by truly random puncturings. In particular, we extend a result of (Guruswami Mosheiff FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed Solomon codes are list-recoverable beyond the Johnson bound, extending a result of (Lund Potukuchi RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime.
翻译:我们引入了一种新颖的基于扩展器的纠错码家族。这些码可以使用线性随机性采样,并实现可列表矫正距离的最大值(以及其他局部性质)。我们可以从任何足够低偏差码的家族开始制作扩展器基本码,因此,我们首次构建了一种可以使用线性随机性抽样并实现可列表矫正容量的代数码的家族。我们通过引入伪随机码的切割概念来实现这一目的,其中我们通过在$[m]$上的图上的扩展器随机游走选择一个基本码$C\subset \mathbb{F}_q^m$的$n$个索引。具体而言,而随机线性码(即Hadamard码的真随机切割)需要$O(n^2)$随机比特才能采样,我们可以使用$O(n)$随机比特采样伪随机线性码。我们展示了伪随机的切割满足真随机切割所展示的几个理想属性。特别地,我们推广了(Guruswami Mosheiff FOCS 2022)的一个结果,并表明小偏差码的伪随机切割具有相同的局部性质,具有高概率的真随机线性码的局部性质。作为我们技术的进一步应用,我们还展示了伪随机切割的Reed Solomon码可以在Johnson界限之外可列表恢复,从而扩展了(Lund Potukuchi RANDOM 2020) 的结果。我们通过分析具有大距离的码的特性来实现这一点,并表明伪随机切割在这一领域仍然有效。