Locally testable codes and PCPs of almost-linear length
Locally testable codes and PCPs of almost-linear length
复制标题
本地可测试的代码和几乎线性长度的 PCP
DOI：
10.1109/sfcs.2002.1181878
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Sudan
中科院分区：
文献类型：
--
作者：
Oded Goldreich;M. Sudan
局部可测码是纠错码，它允许非常高效的码字测试。具体来说，使用常数数量的（随机）查询，非码字被拒绝的概率与其到码的距离成正比。局部可测码被认为是概率可验证明（PCPs）的组合核心。然而，这种关系比通常认为的要间接。尽管如此，我们表明某些PCP系统可以被修改以产生局部可测码。另一方面，我们调整为构建局部可测码而开发的技术以产生新的PCP。我们的主要结果是几乎线性长度的局部可测码和PCP。具体来说，我们提出：
1. 局部可测（线性）码，其中k个信息位由长度约为k·exp(√(log))的码字编码。这改进了之前的结果，之前的结果要么产生指数长度的码字，要么对于足够大的非二进制字母表获得几乎二次长度的码字。
2. 针对可满足性问题（SAT）的几乎线性长度的PCP系统。证明的长度约为n·exp(√(log n))，并且通过常数数量（即19）的查询进行验证，而之前的结果使用证明长度为n^(1 + O(1/q))通过q次查询进行验证。所使用的新技术包括某些码字和PCP预言机的随机投影，对PCP构造的调整以获得用于证明线性条件合取的“线性PCP预言机”，以及亚指数长度的局部可测（线性）码的直接构造。
Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, noncodewords are rejected with probability proportional to their distance from the code. Locally testable codes are believed to be the combinatorial core of PCPs. However, the relation is less immediate than commonly believed. Nevertheless, we show that certain PCP systems can be modified to yield locally testable codes. On the other hand, we adapt techniques we develop for the construction of the latter to yield new PCPs. Our main results are locally testable codes and PCPs of almost-linear length. Specifically, we present: 1. Locally testable (linear) codes in which k information bits are encoded by a codeword of length approximately k /spl middot/ exp(/spl radic/(log)). This improves over previous results that either yield codewords of exponential length or obtained almost quadratic length codewords for sufficiently large non-binary alphabet. 2. PCP systems of almost-linear length for SAT. The length of the proof is approximately n /spl middot/ exp(/spl radic/(log n)) and verification in performed by a constant number (i.e., 19) of queries, as opposed to previous results that used proof length n/sup 1+O(1/q)/ for verification by q queries. The novel techniques in use include a random projection of certain codewords and PCP-oracles, an adaptation of PCP constructions to obtain "linear PCP-oracles" for proving conjunctions of linear conditions, and a direct construction of locally testable (linear) codes of sub-exponential length.