# 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