Computationally efficient error-correcting codes and holographic proofs

We present computationally efficient error-correcting codes and holographic proofs. Our error-correcting codes are asymptotically good and can be encoded and decoded in linear time. Our construction of holographic proofs provide, for every proof of any theorem, a slightly larger "holographic" proof whose accuracy can be probabilistically checked by an algorithm that only reads a constant number of the bits of the holographic proof and runs in poly-logarithmic time (such proofs have also been called "transparent proofs" and "probabilistically checkable proofs"). We explain how these constructions are related and how improvements of these constructions should result in a strengthening of this relationship.

For every constant r such that $0<r<1,$ we construct an infinite family of systematic linear block error-correcting codes that have an encoding circuit with a linear number of wires. There is a constant $\epsilon>0$ and a linear-time decoding algorithm for these codes that maps every word of relative distance at most $\epsilon$ from a codeword to that codeword. The encoding circuits have logarithmic depth. The decoding algorithm can be implemented as a circuit with $O(n\log\ n)$ wires and logarithmic depth. These constructions make use of explicit constructions of expander graphs and superconcentrators.

Our constructions of holographic proofs improve on the theorem $PCP(\log\ n,1)=NP,$ proved by Arora, Lund, Motwani, Sudan, and Szegedy, by providing, for every $\epsilon>0,$ constant-query checkable proofs of size $O(n\sp{1+\epsilon}).$ That is, we design a probabilistic poly-logarithmic time proof checking algorithm that takes two inputs: a theorem candidate and a proof candidate. After reading a constant number of bits from each input, the proof checker decides whether to accept or reject its inputs. For every rigorous proof of length n of any theorem, there is an easily computable holographic proof of that theorem of size $O(n\sp{1+\epsilon})$ such that, with probability one, the proof checker will accept the holographic proof and an encoding of the theorem. Conversely, if the proof checker accepts a theorem candidate and a proof candidate with probability greater than one-half, then the theorem candidate is close to a unique encoding of a true theorem and the proof candidate constitutes a proof of that theorem. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)