Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR07-016 | 9th March 2007 00:00


Revision #1
Accepted on: 9th March 2007 00:00
Downloads: 3646



TR07-016 | 13th February 2007 00:00

A Note on Yekhanin's Locally Decodable Codes

Authors: Prasad Raghavendra
Publication: 5th March 2007 20:34
Downloads: 3893


Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p = 2^t -1$, binary LDCs of length $2^{O(n^{1/t})}$ for infinitely many $n$ were obtained. Using the largest known Mersenne prime, this implies LDCs of length less than $2^{O(n^{10^{-7}})}$. Assuming infinitude of Mersenne primes, the construction yields LDCs of length $2^{O(n^{1/\log \log n})}$ for infinitely many $n$.

Inspired by the breakthrough, we construct $3$-query binary LDCs with same parameters from Mersenne primes. While all the main technical tools are borrowed from Yekhanin's construction, we give a self-contained simple construction of LDCs. Our bounds do not improve over Yekhanin's, and have worse soundness of the decoder. However the LDCs are simple and generalize naturally to prime fields other than $\Ftwo = \{0,1\}$.
The LDCs presented also translate directly in to three server Private Information Retrieval(PIR) protocols with communication complexities $O(n^{1/t})$ for a database of size $n$, starting with a Mersenne prime $p = 2^{t} -1$.

ISSN 1433-8092 | Imprint