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 E > 0 and a linear-time decoding algorithm for these codes that maps every word of relative distance at most E 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 E > 0, constant-query checkable proofs of size O(n 1 +'). That is, we design a probabilistic polylogarithmic 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(nl+e) 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.