Corruption and Recovery-Efficient Locally Decodable Codes

Abstract

A (q, δ, ε)-locally decodable code (LDC) C: {0,1}ⁿ →{0,1}^m is an encoding from n-bit strings to m-bit strings such that each bit x _k can be recovered with probability at least $\frac{1}{2} + \epsilon$ from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to δm positions of C(x) are corrupted. If C is a linear map, then the LDC is linear. We give improved constructions of LDCs in terms of the corruption parameter δ and recovery parameter ε. The key property of our LDCs is that they are non-linear, whereas all previous LDCs were linear.

• 1 For any δ, ε ∈ [Ω(n ^− 1/2), O(1)], we give a family of (2, δ, ε)-LDCs with length . For linear (2, δ, ε)-LDCs, Obata has shown that $m \geq \exp \left (\delta n \right )$. Thus, for small enough constants δ, ε, two-query non-linear LDCs are shorter than two-query linear LDCs.

• 1 We improve the dependence on δ and ε of all constant-query LDCs by providing general transformations to non-linear LDCs. Taking Yekhanin’s linear (3, δ, 1/2 − 6δ)-LDCs with $m = \exp \left (n^{1/t} \right )$ for any prime of the form 2^t − 1, we obtain non-linear (3, δ, ε)-LDCs with .

Now consider a (q, δ, ε)-LDC C with a decoder that has n matchings M ₁, ..., M _n on the complete q-uniform hypergraph, whose vertices are identified with the positions of C(x). On input k ∈ [n] and received word y, the decoder chooses e = {a ₁, ..., a _q } ∈ M _k uniformly at random and outputs $\bigoplus_{j=1}^q y_{a_j}$. All known LDCs and ours have such a decoder, which we call a matching sum decoder. We show that if C is a two-query LDC with such a decoder, then $m \geq \exp \left (\max(\delta, \epsilon)\delta n \right )$. Interestingly, our techniques used here can further improve the dependence on δ of Yekhanin’s three-query LDCs. Namely, if δ ≥ 1/12 then Yekhanin’s three-query LDCs become trivial (have recovery probability less than half), whereas we obtain three-query LDCs of length $\exp \left (n^{1/t} \right )$ for any prime of the form 2^t − 1 with non-trivial recovery probability for any δ< 1/6.