We present the first explicit construction of Probabilistically Checkable Proofs
(PCPs) and Locally Testable Codes (LTCs) of fixed constant query complexity which
have almost-linear size. Such objects were recently shown to exist
(nonconstructively) by Goldreich and Sudan.

The key to these constructions is a nearly optimal randomness-efficient version of
the Rubinfeld-Sudan low degree test. The original test uses a random line in the
given vector space. The number of such lines is quadratic in the size of the space,
which implied a similar blow up in previous constructions of LTCs. Goldreich and
Sudan showed that there exists a nearly linear sized sample space of lines such
that running the low-degree test on a random line from this collection is a good
test. We give an explicit sample space with this property.

In a similar way we give a randomness-efficient version of the Blum-Rubinfeld-Sudan
linearity test (which is used, for instance, in locally testing the Hadamard code).

Both derandomizations are obtained through epsilon-biased sets for vector spaces over
finite fields.The sample space consists of the lines defined by the edges of the Cayley
expander graph generated by the epsilon-biased set.

The analysis of the derandomized tests rely on alternative views of epsilon-biased sets
--- as generating sets of Cayley expander graphs for the low degree test, and as
defining good linear error-correcting codes for the linearity test.

Joint work with Eli Ben-Sasson, Madhu Sudan and Salil Vadhan