An optimal lower bound for 2-query locally decodable linear codes

被引：6
|
作者：
Shiowattana, D [1 ]
Lokam, SV [1 ]
机构：
[1] Univ Michigan, Dept Elect Engn & Comp Sci, Ann Arbor, MI 48109 USA
来源：
INFORMATION PROCESSING LETTERS | 2006年 / 97卷 / 06期
基金：
美国国家科学基金会;
关键词：
combinatorial problems; computational complexity; cryptography;
D O I：
10.1016/j.ipl.2005.11.009
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The lower bound of Obata yielding a bound that is optimal up to a constant factor for 2-query locally decodable linear codes (LCD), is described. The first step shows that any 2-query linear LDC must be defined by a set of points in the n-dimensional Boolean cube such that, for each of the n dimensions. The second step shows that any set that has large matchings along each of the n dimensions must necessarily be large. An exponential bound is achieved, optimal up to a constant factor in the exponent.
引用
收藏
页码：244 / 250
页数：7
相关论文
共 50 条
12345