Nearly linear-size holographic proofs

Authors: Alexander Polishchuk and Daniel A. Spielman.

Bibliographic Information: First appeared in the Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 194-203.

Abstract

We show how to construct holographic (or transparent) proofs of size $n^{1+\epsilon }$ that can be checked by a verifier that is allowed to read only $\O{1}$ bits of the proof and has access to $\O{\log n}$ random bits, for all $\epsilon >0$. In general, we construct proofs of size $n^{1+2^{-\O{q(n)}}}(\log n)^{\O{q(n)}}$ checkable by the query of $2^{\O{q(n)}}$ bits, for any $q(n) = \O{\log \log n}$. An essential element of our construction is a proof that the low-degree test used by Arora and Safra is effective on domains of size linear in the degree of the encoded polynomial.

You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.

Daniel A. Spielman

Last modified: Fri Aug 24 15:49:01 2001