New Locally Decodable Codes and Private Information Retrieval Schemes

Sergey Yekhanin (MIT CSAIL)

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 x_i 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=2^t-1, we design three query LDCs of length N=EXP(n^{1/t}), for every $n$. Based on the largest known Mersenne prime, this translates to a length of less than EXP(n^{10^{-7}}), compared to EXP(n^{1/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(n^{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(n^{10^{-7}}) to access an n-bit database, compared to the previous best scheme with complexity O(n^{1/5.25}). Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexity n^{O(1/log log n)} 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.

Host: Madhu Sudan

(The Algorithms and Complexity Seminar series talks are usually held Mondays from 4-5:15pm in 32-G575.)