Towards 3-query locally decodable codes of subexponential length
Towards 3-query locally decodable codes of subexponential length
复制标题
面向次指数长度的 3 查询本地可解码代码
DOI：
10.1145/1250790.1250830
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Yekhanin
中科院分区：
文献类型：
--
作者：
S. Yekhanin
Q-查询局部可解码码(LDC)将一个n比特的消息x编码为一个n比特的码字C(X)，这样，即使在码字C(X)的一些恒定分数的码字比特已经被破坏之后，也可以通过只查询码字C(X)的Q比特来概率地恢复消息的任何比特xi。具体地说，给定任何Mersenne素数p=2t-1，对于每个n，我们设计了三个长度为N=(n1/t)的查询LDC。基于已知的最大Mersenne素数，这转化为小于exp(n10-7)的长度，而不是先前构造中的exp(n1/2)。人们经常猜想存在无限多个梅森素数。在这个猜想下，对于无限多个n，我们的构造产生了三个长度为N=exp(no(1/(Loglogn)的可查询局部可译码。
对于私有信息检索(PIR)方案，我们也得到了类似的改进。我们给出了通信复杂度为O(n10-7)的3服务器PIR方案来访问n位数据库，而以前的最佳方案的通信复杂度为O(n1/5.25)。再次假设存在无限多个Mersenne素数，我们得到了通信复杂度为no(1/(Loglogn))的无穷多个n的3-服务PIR方案。
以往的最不发达国家族和PIR方案都是基于有限域上低次多元多项式的性质。我们的构造是完全不同的，是通过在一个小的维向量空间中构造大量的向量而得到的，该向量的内积被限制在一个代数良好的集合中。
A 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 bits has been corrupted.We give new constructions of three query LDCs of vastly shorterlength than that of previous constructions. Specifically, givenany Mersenne prime p = 2t - 1, we design three query LDCs of length N=(n1/t), for every n. Based on thelargest known Mersenne prime, this translates to a length of less than exp(n10-7), compared to exp(n1/2) in the previous constructions. It hasoften been conjectured that there are infinitely many Mersenneprimes. Under this conjecture, our constructions yield three querylocally decodable codes of length N=exp(nO(1/(log log n))) forinfinitely many n.
We also obtain analogous improvements for Private InformationRetrieval (PIR) schemes. We give 3-server PIR schemes withcommunication complexity of O(n10-7) to accessan n-bit database, compared to the previous best scheme withcomplexity O(n1/5.25). Assuming again that there areinfinitely many Mersenne primes, we get 3-server PIR schemes ofcommunication complexity nO(1/(log log n))for infinitely many n.
Previous families of LDCs and PIR schemes were based on theproperties of low-degree multivariate polynomials over finitefields. Our constructions are completely different and areobtained by constructing a large number of vectors in a smalldimensional vector space whose inner products are restricted tolie in an algebraically nice set.