High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
复制标题
具有次多项式查询复杂度的高速本地可校正和本地可测试代码
DOI：
10.1145/3051093
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Shubhangi Saraf
中科院分区：
文献类型：
--
作者：
Swastik Kopparty;Or Meir;Noga Ron;Shubhangi Saraf
局部可纠错码（LCCs）和局部可验错码（LTCs）是纠错码，它们允许使用局部算法来纠错和检测错误。这些算法是局部的，意思是它们只查询被破坏的码字中的少量条目。关于LCCs和LTCs的基本问题是确定它们的码率、距离和查询复杂度之间的最优权衡。在这项工作中，我们构造了首批具有恒定码率、恒定相对距离和次多项式查询复杂度的LCCs和LTCs。具体来说，我们表明存在块长度为\(n\)、恒定码率（甚至可以任意接近\(1\)）和恒定相对距离的LCCs和LTCs，其查询复杂度对于LCCs是\(\exp(\widetilde{O}(\sqrt{\log n}))\)，对于LTCs是\((\log n)^{O(\log\log n)}\)。除了具有较小的查询复杂度外，我们的编码在码率和相对距离之间也实现了比之前已知的LCCs或LTCs所能达到的更好的权衡。具体来说，在大（但大小恒定）的字母表上，我们的编码接近辛格尔顿界，也就是说，它们在码率和距离之间具有几乎最佳的关系。在二进制字母表上，我们的编码符合齐亚布洛夫界。对于任何\(o(n)\)查询复杂度，之前都不知道码率和相对距离之间存在这样的权衡。我们关于LCCs的结果也立即给出了具有相同参数的局部可解码。
Locally correctable codes (LCCs) and locally testable codes (LTCs) are error-correcting codes that admit local algorithms for correction and detection of errors. Those algorithms are local in the sense that they only query a small number of entries of the corrupted codeword. The fundamental question about LCCs and LTCs is to determine the optimal tradeoff among their rate, distance, and query complexity. In this work, we construct the first LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1), and constant relative distance, whose query complexity is exp(Õ(√log n)) (for LCCs) and (log n)O(log log n) (for LTCs). In addition to having small query complexity, our codes also achieve better tradeoffs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. Over the binary alphabet, our codes meet the Zyablov bound. Such tradeoffs between the rate and the relative distance were previously not known for any o(n) query complexity. Our results on LCCs also immediately give locally decodable codes with the same parameters.