Publication: Randomness-Efficient Low-Degree Tests and Short PCPs Via Epsilon-Biased Sets
Open/View Files
Date
2003
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
Association for Computing Machinery
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Ben-Sasson, Eli, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the 35th Annual ACM Symposium on the Theory of Computing: San Diego, California, USA, June 9-11, 2003, 612-621. New York, NY: ACM Press.
Research Data
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.
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service