A note on Efremenko's Locally Decodable Codes.
Parikshit Gopalan · Electronic colloquium on computational complexity · 2009
There have been three beautiful recent results on constructing short locally decodable codes or LDCs [Yek07, Rag07, Efr09], culminating in the construction of LDCs of sub-exponential length. The initial breakthrough was due to Yekhanin who constructed 3-query LDCs of sub-exponential length, assuming the existence of infinitely many Mersenne primes [Yek07]. Raghavendra presented a clean formulation of Yekhanin’s codes in terms of group homomorphisms [Rag07]. Building on these works, Efremenko recently gave an elegant construction of 3-query LDCs which achieve subexponential length unconditionally [Efr09]. In this note, we observe that Efremenko’s construction can be viewed in the framework of ReedMuller codes: the code consists of a linear subspace of polynomials in Fq[X1, . . . , Xn], evaluated at all points in (Fq). We stress that this is not a new construction, but just a different view of [Efr09]. In this view, the decoding algorithm is similar to traditional local decoders for Reed-Muller codes, where the decoder essentially shoots a line in a random direction and decodes along it (see for instance [STV01]). The difference is that the monomials which are used are not of low-degree, they are chosen according to a suitable set-system. Further, the lines for decoding are multiplicative, a notion we will define shortly. A crucial ingredient in these LDCs is a large matching set of vectors over Zm. Such vectors can be obtained from the set-systems with restricted intersections modulo composites constructed by Grolmusz [Gro00]. His construction uses the low-degree representations of the OR function modulo composites [BBR94]. We present a construction of matching vectors directly from OR polynomials due to Sudan [Sud09], which is very simple and achieves nearly the same parameters.