Near-linear time decoding of Ta-Shma’s codes via splittable regularity
Near-linear time decoding of Ta-Shma’s codes via splittable regularity
复制标题
通过可分割正则性对 Ta-Shma 码进行近线性时间解码
DOI：
10.1145/3406325.3451126
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tulsiani, Madhur
中科院分区：
文献类型：
--
作者：
Jeronimo, Fernando Granha;Srivastava, Shashank;Tulsiani, Madhur
Gilbert-Varshamov界非建设性地建立了距离为1/2− 1/2和速率为Ω（1/2）的二进制码的存在性。在一个突破性的结果中，Ta-Shma [STOC 2017]构建了第一个近似最优二进制码的显式族，距离为1/2− n/2，速率为Ω（n = 2+α），其中α → 0为n = 0。此外，Ta-Shma构造中的代码是双平衡的，其中不同码字之间的距离不仅从下到上由1/2 − N/2界定，而且从上到下由1/2+ N/2界定。这些算法的运行时间的形式是NO α（1），用于唯一解码，和NO α，α（1），用于“温和列表解码”的设置，具有N的大指数，即使α是固定常数。我们推导出这两个任务的新算法，在时间上运行。我们的算法也适用于一般设置的解码直和codes.Our算法遵循新的结构和算法的结果集合ofk-元组（有序超图）拥有一个“结构化的扩展”的属性，我们称之为splittability。这个属性以前被识别并用于基于SOS的解码和约束满足算法的分析中，并且也被Ta-Shma的代码构造所满足。我们得到了一个新的弱正则性分解（可能稀疏）可分裂集合W <$[n]k，类似于Frieze和Kannan [FOCS 1996]稠密结构的正则性分解。这些分解也可以在近线性时间内计算（|W|），并形成我们的算法结果的关键组成部分。
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 firstexplicitfamily 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 formNOα(1)for unique decoding, andNOє,α(1)for the setting of “gentle list decoding”, with large exponents ofNeven 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 direct-sum codes.Our algorithms follow from new structural and algorithmic results for collections ofk-tuples (ordered hypergraphs) possessing a “structured expansion” property, which we callsplittability. 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 decomposition for (possibly sparse) splittable collectionsW⊆ [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 Õ(|W|), and form a key component of our algorithmic results.
登录
查看更多内容
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
发表时间：
2011
期刊：
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Barak;P. Raghavendra;David Steurer
通讯作者：
David Steurer
通过高维扩展器进行本地可测试代码
DOI：
--
发表时间：
2020
期刊：
Electronic colloquium on computational complexity
影响因子：
--
作者：
Dikstein, Y;Dinur, I;Harsha, P;Ron-Zewi, N.
通讯作者：
Ron-Zewi, N.
每个维度的有界度共收缩扩张器
DOI：
--
发表时间：
2015
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Shai Evra;T. Kaufman
通讯作者：
T. Kaufman
DOI：
--
发表时间：
1996
期刊：
Proceedings of 37th Conference on Foundations of Computer Science
影响因子：
--
作者：
A. Frieze;R. Kannan
通讯作者：
R. Kannan
DOI：
--
发表时间：
2004
期刊：
SIGA
影响因子：
--
作者：
V. Guruswami
通讯作者：
V. Guruswami