Pseudorandom Linear Codes are List Decodable to Capacity
Pseudorandom Linear Codes are List Decodable to Capacity
复制标题
伪随机线性码可按容量解码列表
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Edward Pyne
中科院分区：
文献类型：
--
作者：
Aaron Putterman;Edward Pyne
我们引入了一系列新颖的基于扩展器的纠错码。这些代码可以在块长度上以线性随机性进行采样，并实现列表解码能力（以及其他本地属性）。我们基于扩展器的代码可以从任何足够低偏差的代码族开始制作，因此，我们给出了代数代码族的第一个构造，该代数代码可以以线性随机性采样并实现列表解码能力。我们通过引入代码伪随机打孔的概念来实现这一点，其中我们通过在 $[m]$ 上的图上进行扩展器随机游走来选择基本代码 $Csubset mathbb{F}_q^m$ 的 $n$ 索引。具体来说，随机线性码（即哈达玛码的真正随机删截）需要 $O(n^2)$ 随机位进行采样，而我们使用 $O(n)$ 随机位对伪随机线性码进行采样。我们证明伪随机穿孔满足真正随机穿孔所表现出的几个理想特性。特别是，我们扩展了（Guruswami Mosheiff FOCS 2022）的结果，并表明小偏差码的伪随机删截以高概率满足与随机线性码相同的局部属性。作为我们技术的进一步应用，我们还证明了里德所罗门码的伪随机穿孔是可恢复的，超出了约翰逊界限，扩展了（Lund Potukuchi RANDOM 2020）的结果。我们通过分析大距离代码的属性来做到这一点，并表明伪随机穿孔在这种情况下仍然有效。
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 $Csubset 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.
LDPC码实现列表解码能力
DOI：
10.1109/focs46700.2020.00050
发表时间：
2020
期刊：
Foundations of Computer Science (FOCS 2020
影响因子：
--
作者：
Mosheiff, Jonathan;Resch, Nicolas;Ron-Zewi, Noga;Silas, Shashwat;Wootters, Mary
通讯作者：
Wootters, Mary
通过可分割正则性对 Ta-Shma 码进行近线性时间解码
DOI：
10.1145/3406325.3451126
发表时间：
2021
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Jeronimo, Fernando Granha;Srivastava, Shashank;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur
随机线性码的列表解码和列表恢复的界限
DOI：
10.4230/lipics.approx/random.2020.9
发表时间：
2020
影响因子：
--
作者：
Guruswami, Venkatesan;Li, Ray;Mosheiff, Jonathan;Resch, Nicolas;Silas, Shashwat;Wootters, Mary
通讯作者：
Wootters, Mary