### Locally testable codes and PCPs of almost-linear lengthLocally testable codes and PCPs of almost-linear length

Access Restriction
Subscribed

 Author Goldreich, Oded ♦ Sudan, Madhu Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2006 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Proof verification ♦ Derandomization ♦ Error-correcting codes ♦ Probabilistically checkable proofs Abstract We initiate a systematic study of locally testable codes; that is, error-correcting codes that admit very efficient membership tests. Specifically, these are codes accompanied with tests that make a constant number of (random) queries into any given word and reject non-codewords 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 that 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 prove the existence of the following constructs:---Locally testable binary (linear) codes in which $\textit{k}$ information bits are encoded by a codeword of length $\textit{k}$ ṡ exp(Õ(√(log $\textit{k}))).$ This improves over previous results that either yield codewords of exponential length or obtained almost quadratic length codewords for sufficiently large nonbinary alphabet.---PCP systems of almost-linear length for SAT. The length of the proof is $\textit{n}$ ṡ exp(Õ(√(log $\textit{n})))$ and verification in performed by a constant number (i.e., 19) of queries, as opposed to previous results that used proof length $\textit{n}(1$ + $\textit{O}(1/\textit{q}))$ for verification by $\textit{q}$ queries.The novel techniques in use include a random projection of certain codewords and PCP-oracles that preserves local-testability, an adaptation of PCP constructions to obtain “linear PCP-oracles” for proving conjunctions of linear conditions, and design of PCPs with some new soundness properties---a direct construction of locally testable (linear) codes of subexponential length. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2006-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 53 Issue Number 4 Page Count 98 Starting Page 558 Ending Page 655

#### Open content in new tab

Source: ACM Digital Library