论文标题
带有改进参数的本地校正代码放松
Relaxed Locally Correctable Codes with Improved Parameters
论文作者
论文摘要
可局部解释的代码（LDC）是错误校正的代码$ c：σ^k \ toσ^n $，该代码接纳了局部解码算法，该算法仅通过从噪声代码字中查询几个位来恢复消息的每个单个位。在这一研究中，一个重要的问题是了解最佳的麻省理运动物的查询复杂性与其块长度之间的最佳权衡。尽管这些对象很重要，但最著名的恒定查询构造的构造具有超顺式长度，并且在块长度方面，最佳结构和已知的下限之间存在显着差距。 对于许多应用，可以考虑放松的最不发达国家（RLDC）的较弱概念，这允许局部解码算法可以流产，如果通过查询一些位，它检测到输入不是密码字。事实证明，这种放松允许对几乎线性长度的代码的恒定查询复杂性进行解码算法。具体来说，[BGH+06]使用块长度的代码字$ n = o（k^{1+1/\ sqrt {q}}}）$构造了一个$ o（q）$ - 查询rldc，该$ QUERY RLDC编码长度$ k $的消息。 在这项工作中，我们通过构造$ o（q）$ - 查询rldc来改善[bgh+06]的参数，该$ o（q）$ - 使用块长度$ o（k^{1+1/{q}}）$编码长度$ k $的消息。该构造匹配（最多达到乘法常数因子），用于常量查询的[KT00，WOO07]的下限，从而在恒定查询方面朝着理解LDC和RLDC之间的差距方面取得了进展。 实际上，我们的构造扩展到[GRR18]中引入的更强烈的本地校正代码（RLCC）的更强的概念，在此，鉴于嘈杂的代码字校正算法，校正算法要么仅通过读取输入的一小部分或中止输入而恢复了代码字的每个单个位，要么如果输入损坏了。
Locally decodable codes (LDCs) are error-correcting codes $C : Σ^k \to Σ^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off between the query complexity of LDCs and their block length. Despite importance of these objects, the best known constructions of constant query LDCs have super-polynomial length, and there is a significant gap between the best constructions and the known lower bounds in terms of the block length. For many applications it suffices to consider the weaker notion of relaxed LDCs (RLDCs), which allows the local decoding algorithm to abort if by querying a few bits it detects that the input is not a codeword. This relaxation turned out to allow decoding algorithms with constant query complexity for codes with almost linear length. Specifically, [BGH+06] constructed an $O(q)$-query RLDC that encodes a message of length $k$ using a codeword of block length $n = O(k^{1+1/\sqrt{q}})$. In this work we improve the parameters of [BGH+06] by constructing an $O(q)$-query RLDC that encodes a message of length $k$ using a codeword of block length $O(k^{1+1/{q}})$. This construction matches (up to a multiplicative constant factor) the lower bounds of [KT00, Woo07] for constant query LDCs, thus making progress toward understanding the gap between LDCs and RLDCs in the constant query regime. In fact, our construction extends to the stronger notion of relaxed locally correctable codes (RLCCs), introduced in [GRR18], where given a noisy codeword the correcting algorithm either recovers each individual bit of the codeword by only reading a small part of the input, or aborts if the input is detected to be corrupt.
