Sergey Yekhanin
Abstract
A q-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit xi of the message by querying only q bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted.
We give new constructions of three query LDCs of vastly shorter length than that of previous constructions. Specifically, given any Mersenne prime p = 2t − 1, we design three query LDCs of length N = exp(O(n1/t)), for every n. Based on the largest known Mersenne prime, this translates to a length of less than exp(O(n10 − 7)) compared to exp(O(n1/2)) in the previous constructions. It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of length N = exp(nO(1/log log n)) for infinitely many n.
We also obtain analogous improvements for Private Information Retrieval (PIR) schemes. We give 3-server PIR schemes with communication complexity of O(n10 − 7) to access an n-bit database, compared to the previous best scheme with complexity O(n1/5.25). Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexity nO(1/log logn)) for infinitely many n.
Previous families of LDCs and PIR schemes were based on the properties of low-degree multivariate polynomials over finite fields. Our constructions are completely different and are obtained by constructing a large number of vectors in a small dimensional vector space whose inner products are restricted to lie in an algebraically nice set.
- Ambainis, A. 1997. Upper bound on the communication complexity of private information retrieval. In Proceedings of the 32nd Annual International Colloquium on Antomata, Languages and Programming. Lecture Notes in Computer Science, vol. 1256, Springer-Verlag, New York, pp. 401--407. Google Scholar
Digital Library
- Babai, L., Fortnow, L., Levin, L., and Szegedy, M. 1991. Checking computations in polylogarithmic time. In Proceedings of the 23th ACM Symposium on Theory of Computing (STOC). ACM, New York, pp. 21--31. Google ScholarDigital Library
- Babai, L., and Frankl, P. 1998. Linear algebra methods in combinatorics.Google Scholar
- Beigel, R., Fortnow, L., and Gasarch, W. 2006. A tight lower bound for restricted PIR protocols. Computat. Complex 15, 82--91. Google ScholarDigital Library
- Beimel, A., Ishai, Y., and Kushilevitz, E. 2005. General constructions for information-theoretic private information retrieval. J. Comput. Syst. Sci. 71, 213--247, (Preliminary versions in STOC 1999 and ICALP 2001.) Google ScholarDigital Library
- Beimel, A., Ishai, Y., Kushilevitz, E., and Raymond, J. F. 2002. Breaking the O(n
1/(2k − 1)) barrier for information-theoretic private information retrieval. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, pp. 261--270. Google ScholarDigital Library
- Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. 1995. Private information retrieval. In Proceedings of the 36rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, pp. 41--50. (Also, in J. ACM 45, 1998). Google ScholarDigital Library
- Deshpande, A., Jain, R., Kavitha, T., Lokam, S., and Radhakrishnan, J. 2002. Better lower bounds for locally decodable codes. In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). IEEE Computer Society Press, Los Alamitos, CA, pp. 184--193. Google ScholarDigital Library
- Cooper, C., and Boone, S. 2006. http://www.mersenne.org/32582657.htm.Google Scholar
- Gasarch, W. 2004. A survey on private information retrieval. Bull. EATCS 82, 72--107.Google Scholar
- Goldreich, O. 2005. Short locally testable codes and proofs. Tech. Rep. TR05-014. In Proceedings of the Electronic Colloquim on Computational Complexity (ECCC).Google Scholar
- Goldreich, O., Karloff, H., Schulman, L., and Trevisan, L. 2006. Lower bounds for locally decodable codes and private information retrieval. Computat. Complex. 15, 3, 263--296. Google ScholarDigital Library
- Itoh, T. 1999. Efficient private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E82-A, 1, 11--20.Google Scholar
- Itoh, T. 2001. On lower bounds for the communication complexity of private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E84-A1, 157--164.Google Scholar
- Kedlaya, K., and Yekhanin, S. 2007. Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-040.Google Scholar
- Katz, J., and Trevisan, L. 2000. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the 32th ACM Symposium on Theory of Computing (STOC). ACM, New York, pp. 80--86. Google ScholarDigital Library
- Kerenidis, I., and de Wolf, R. 2003. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. 69, 3, 395--420. (Earlier version in STOC'03. quant-ph/0208062.) Google ScholarDigital Library
- Lenstra, Jr., H. W. 1980. Primarlity testing. In Studieweek Getaltheorie en Computers (Sept. 1--5). Stichting Math., Centrum, Amsterdam, The Netherlands.Google Scholar
- Lidl, R., and Niederreiter, H. 1983. Finite Fields. Cambridge University Press, Cambridge, MA.Google Scholar
- Mann, E. 1998. Private access to distributed information. Master's thesis, Technion - Israel Institute of Technology, Haifa, Israel.Google Scholar
- Obata, K. 2002. Optimal lower bounds for 2-query locally decodable linear codes. In Proceedings of the 6th International Workshop on Randomization Techniques: Lecture Notes in Computer Science, vol. 2483. Springer-Verlag, New York, pp. 39--50. Google ScholarDigital Library
- Polishchuk, A., and Spielman, D. 1994. Nearly-linear size holographic proofs. In Proceedings of the 26th ACM Symposium on Theory of Computing (STOC). ACM, New York, pp. 194--203. Google ScholarDigital Library
- Pomerance, C. 1980/81. Recent developments in primality testing. Math. Intell. 3, 3, 97--105.Google ScholarCross Ref
- Razborov, A., and Yekhanin, S. 2006. An Ω(n
1/3) lower bound for bilinear group based private information retrieval. In Proceedings of the 47rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 739--748. Google ScholarDigital Library
- Sudan, M. 1992. Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. dissertation, University of California at Berkeley, Berkeley, CA. Google ScholarDigital Library
- Trevisan, L. 2004. Some applications of coding theory in computational complexity. Quad. Matemat. 13, 347--424.Google Scholar
- Wehner, S., and de Wolf, R. 1997. Improved lower bounds for locally decodable codes and private information retrieval. In Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP'05). Lecture Notes in Computer Science, vol. 3580, Springer-Verlag, New York, pp. 1424--1436. Google ScholarDigital Library
- Wagstaff, S. 1983. Divisors of Mersenne numbers. Math. Comput. 40, 161, 385--397.Google Scholar
- Woodruff, D. 2007. New lower bounds for general locally decodable codes. In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-006.Google Scholar
- Woodruff, D., and Yekhanin, S. 2007. A geometric approach to information theoretic private information retrieval. SIAM J. Comput. 37, 4, 1046--1056. Google ScholarDigital Library
- Yekhanin, S. 2006. New locally decodable codes and private infromation retrieval schemes. In Electronic Colloquium on Computational Complexity, Tech. rep. TR06-127.Google Scholar
Index Terms
- Towards 3-query locally decodable codes of subexponential length
Recommendations
3-query locally decodable codes of subexponential length
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingLocally 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-...
Towards 3-query locally decodable codes of subexponential length
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computingA q-query Locally Decodable Code (LDC) encodes an n-bitmessage x as an n-bit codeword C(x), such that one canprobabilistically recover any bit xi of the message by queryingonly q bits of the codeword C(x), even after some constantfraction of codeword ...
Query-Efficient Locally Decodable Codes of Subexponential Length
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 ...
Comments