Access Restriction

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

   Open content in new tab
Source: ACM Digital Library