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 ]