论文标题
随机编码的本地可解码代码
Locally Decodable Codes with Randomized Encoding
论文作者
论文摘要
我们启动了具有随机编码的本地可解码代码的研究。标准可局部解释的代码是具有确定性编码函数和随机解码功能的错误纠正代码，以便可以通过在损坏的代码字中查询少量位置，以良好的概率恢复任何所需的消息位。这允许人们在子线性甚至对数时间中非常有效地恢复任何消息。除了这个直接的应用程序外，本地可解码的代码还发现了许多其他应用程序，例如私人信息检索，安全的多方计算和平均案例复杂性。 但是，尽管进行了广泛的研究，但《法规率与查询数量》之间的权衡令人失望。例如，即使使用对数的查询数量，最著名的构建体仍然需要超级多条的代码字长度，并且需要多项式的查询来达到恒定速率。在本文中，我们表明，通过使用随机编码，在几种模型中，我们可以实现更高的费率折衷方案。此外，我们的代码都适用于标准锤误差，以及更通用和更难的编辑错误。
We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a small number of positions in the corrupted codeword. This allows one to recover any message bit very efficiently in sub-linear or even logarithmic time. Besides this straightforward application, locally decodable codes have also found many other applications such as private information retrieval, secure multiparty computation, and average-case complexity. However, despite extensive research, the tradeoff between the rate of the code and the number of queries is somewhat disappointing. For example, the best known constructions still need super-polynomially long codeword length even with a logarithmic number of queries, and need a polynomial number of queries to achieve a constant rate. In this paper, we show that by using a randomized encoding, in several models we can achieve significantly better rate-query tradeoff. In addition, our codes work for both the standard Hamming errors, and the more general and harder edit errors.
