Randomness-efficient low-degree tests and short PCPs
via epsilon-biased sets
Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson
Abstract
We present the first explicit construction of Probabilistically Checkable Proofs (PCPs) and Locally TestableCodes (LTCs) of fixed constant query complexity which
have almost-linear (=n^{1+o(1)}) size. Such objects were recently shown to exist (nonconstructively) by Goldreich and
Sudan [2002]. The key to these constructions is a nearly optimal
randomness-efficient version of the low degree test [Rubinfeld & Sudan `96].
In a similar way we give a randomness-efficient version of the BLR linearity
test [Blum, Luby, Rubinfeld `93] (which is used, for instance, in locally testing
the Hadamard code). The derandomizations are obtained through \eps-biased sets for
vector spaces over finite fields. The analysis of the derandomized tests
rely on alternative views of \eps-biased sets --- as generating sets of Cayley expander graphs for the low-degree test, and
as defining linear error-correcting codes for the linearity test.
Versions
[
back to Salil Vadhan's research interests ]