Lower Bounds for 2-Query LCCs over Large Alphabet
Lower Bounds for 2-Query LCCs over Large Alphabet
复制标题
大字母表上 2 查询 LCC 的下界
DOI：
10.4230/lipics.approx-random.2017.30
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Avishay Tal
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;Sivakanth Gopi;Avishay Tal
局部更正的代码（LCC）是一个错误纠正代码，仅通过查询少数坐标来校正损坏的代码字的任何任意坐标。我们表明任何{\ em Zero-error} $ 2 $ 2 $ - Query在本地更正代码$ \ MATHCAL {C}：\ {0,1 \}^k \ to \ sigma^n $，可以纠正不断损坏的符号的常数分数必须具有$ n \ geq \ exp（k/\ log | \ sigma |）$。我们说，如果存在一种非自适应校正算法，则LCC为零，该算法在未损坏的代码字中，以概率为$ 1 $成功。 LCC的所有已知构造均为零错误。
我们的结果是指数中的恒定因素。由于Katz和Trevisan引起的（STOC 2000），在大型字母上的2 Query LCC长度上唯一的下限是$ \ omega \ left（（k/\ log | \ sigma |）^2 \ right）$（STOC 2000）。我们的界限意味着零错误的LCC不能产生$ 2 $ Server的私人信息检索（PIR）方案（PIR）方案，并带有亚物质通信。由于存在基于零误差$ 2 $ 2 $ Query本地可解码的代码（LDC）的$ 2 $ SERVER PIR计划（STOC 2015），因此我们还获得了大型字母内的LDC和LCC之间的分离。
为了证明结果的证明，我们需要一个新的分解引理，用于可能具有独立感兴趣的定向图。鉴于一个密集的有向图$ g $，我们的分解使用了由于Alon和Shapira而导致的Szemer \'Edi规律性引理（Stoc 2003），将几乎所有$ g $的所有$ g $都分解为持续数量的子图，这些子图是Edge-扩展或空。
A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates. We show that any {\em zero-error} $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must have $n \geq \exp(k/\log|\Sigma|)$. We say that an LCC is zero-error if there exists a non-adaptive corrector algorithm that succeeds with probability $1$ when the input is an uncorrupted codeword. All known constructions of LCCs are zero-error.
Our result is tight upto constant factors in the exponent. The only previous lower bound on the length of 2-query LCCs over large alphabet was $\Omega\left((k/\log|\Sigma|)^2\right)$ due to Katz and Trevisan (STOC 2000). Our bound implies that zero-error LCCs cannot yield $2$-server private information retrieval (PIR) schemes with sub-polynomial communication. Since there exists a $2$-server PIR scheme with sub-polynomial communication (STOC 2015) based on a zero-error $2$-query locally decodable code (LDC), we also obtain a separation between LDCs and LCCs over large alphabet.
For our proof of the result, we need a new decomposition lemma for directed graphs that may be of independent interest. Given a dense directed graph $G$, our decomposition uses the directed version of Szemer\'edi regularity lemma due to Alon and Shapira (STOC 2003) to partition almost all of $G$ into a constant number of subgraphs which are either edge-expanding or empty.