3-query locally decodable codes of subexponential length

ABSTRACT

Locally Decodable Codes (LDC) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. In a recent work [Yek08] Yekhanin constructs a 3-query LDC with sub-exponential length of size exp(exp(O((log n)/(log log n)))). However, this construction requires a conjecture that there are infinitely many Mersenne primes. In this paper we give the first unconditional constant query LDC construction with subexponantial codeword length. In addition our construction reduces codeword length. We give construction of 3-query LDC with codeword length exp(exp(O(√{log n log log n ))). Our construction could also be extended to higher number of queries. We give a 2^r-query LDC with length of exp(exp(O(☂[r] log n (log log n)^r-1))).

REFERENCES

• 1: Andris Ambainis, Upper Bound on Communication Complexity of Private Information Retrieval, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.401-407, July 07-11, 1997
• 2: Amos Beimel , Yuval Ishai , Eyal Kushilevitz, General constructions for information-theoretic private information retrieval, Journal of Computer and System Sciences, v.71 n.2, p.213-247, August 2005 [doi>10.1016/j.jcss.2005.03.002]
• 3: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.41, October 23-25, 1995
• 4: William I. Gasarch. A survey on private information retrieval (column: Computational complexity). Bulletin of the EATCS, 82:72--107, 2004.
• 5: Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.175, May 21-24, 2002
• 6: Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower bounds for linear locally decodable codes and private information retrieval, Computational Complexity, v.15 n.3, p.263-296, October 2006 [doi>10.1007/s00037-006-0216-3]
• 7: Vince Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica, 20(1):71--86, 2000.
• 8: Toshiya Itoh. Efficient private information retrieval. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E82-A No.1 pp.11--20, 1999.
• 9: Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780560]
• 10: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 11: Kiran S. Kedlaya , Sergey Yekhanin, Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.175-186, June 22-26, 2008 [doi>10.1109/CCC.2008.7]
• 12: Eran Mann. Private access to distributed information. In Master's thesis, Technion -- Israel Institute of Technology, 1998.
• 13: Prasad Raghavendra. A note on yekhanin's locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 2007.
• 14: Alexander A. Razborov and Sergey Yekhanin. An omega(1/3) lower bound for bilinear group based private information retrieval. Theory of Computing, 3(1):221--238, 2007.
• 15: Luca Trevisan. Some applications of coding theory in computational complexity. Electronic Colloquium on Computational Complexity (ECCC), (043), 2004.
• 16: Stephanie Wehner and Ronald de Wolf. Improved lower bounds for locally decodable codes and private information retrieval. In ICALP, pages 1424--1436, 2005.
• 17: David Woodruff. New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 2007.
• 18: David Woodruff, Corruption and Recovery-Efficient Locally Decodable Codes, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_46]
• 19: Sergey Yekhanin, Towards 3-query locally decodable codes of subexponential length, Journal of the ACM (JACM), v.55 n.1, p.1-16, February 2008 [doi>10.1145/1326554.1326555]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
PIR schemes, locally decodable codes, private information retrieval schemes