Query-efficient locally decodable codes of subexponential length - Chee, Yeow Meng (2012)
A k-query locally decodable code (LDC) C : Σn → ΓN encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been corrupted. Yekhanin (2008) constructed a 3-query LDC of subexponential length, N = exp(exp(O(log n/log log n))), under the assumption that there are infinitely many Mersenne primes. Efremenko (2009) constructed a 3-query LDC of length N2=exp(exp(O(√(lognloglogn))) with no assumption, and a 2r -query LDC of length Nr=exp(exp(O(r√(logn(loglogn)^(r-1))), for every integer r ≥ 2. Itoh and Suzuki (2010) gave a composition method in Efremenko’s framework and constructed a 3 · 2r-2-query LDC of length Nr, for every integer r ≥ 4, which improved the query complexity of Efremenko’s LDC of the same length by a factor of 3/4. The main ingredient of Efremenko’s construction is the Grolmusz construction for super-polynomial size set-systems with restricted intersections, over Zm , where m possesses a certain “good” algebraic property (related to the “algebraic niceness” property of Yekhanin (2008)). Efremenko constructed a 3-query LDC based on m = 511 and left as an open problem to find other numbers that offer the same property for LDC constructions.