Paper Info
Title
Towards 3-query locally decodable codes of subexponential length
Abstract
A q-query Locally Decodable Code (LDC) encodes ann-bit messagex as an N -bit codewordC(x), such that one can probabilistically recover any bitxi of the message by querying onlyq bits of the codewordC(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 primep = 2t 1, we design three query LDCs of lengthN = exp n1/t , for every n. Based on the largest known Mersenne prime, this translates to a length of less thanexp n10 7 , compared toexp 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 n O 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 ofO n10 7 to access ann-bit database, compared to the previous best scheme with complexityO(n1/5.25). Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexityn 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 polynomi- als 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.
Year
DOI
Venue
2007
10.1145/1326554.1326555
Journal of The ACM
Keywords
Field
DocType
log log n,codeword c,query ldcs,pir scheme,previous construction,length n,previous best scheme withcomplexity,locally decodable codes,towards 3-query,subexponential length,private information retrieval,mersenne primes,decodable code,3-server pir scheme,mersenne prime,previous family,finite field,locally decodable code,vector space,communication complexity,inner product
Log-log plot,Locally decodable code,Discrete mathematics,Vector space,Combinatorics,Mersenne prime,Code word,Conjecture,Multivariate polynomials,Mathematics
Conference
Volume
Issue
ISSN
55
1
0737-8017
Citations 
PageRank 
References 
33
1.24
17
Authors
1
Name
Order
Citations
PageRank
Sergey Yekhanin198352.33