A key component in recent constructions of short PCPs, is a *PCP of
Proximity* (PCPP, also known as *assignment tester*) for
*Reed-Solomon* codes (see definitions below). In this talk we
describe efficient constructions of such PCPPs and their connection
to new Fast Fourier Transform (FFT) algorithms. Time permitting, we
will describe how to obtain the PCP Theorem given solutions to our
problem. The talk is intended for a general audience with CS
background.

The *Reed-Solomon* code of degree d over finite field F is the set
of functions p:F->F that are polynomials of degree at most d.
Reed-Solomon codes have numerous applications in theoretical
computer science and are heavily used in practice.

Let C be a set of functions with range R and domain D (in our case,
C is the Reed-Solomon code and R=D=F) A *PCPP* for C allows a
(randomized polynomial time) *verifier* to probe a function f:R->D
and auxiliary proof (of proximity) on few locations and distinguish
between the case that f belongs to C and the case that f is far (in
Hamming distance) from *any* function in C. In the first case (f in
C), there exists a "good" proof oracle such that f is accepted by
the verifier with probability one. In the second case (f far from
C), the verifier rejects f with probability 1/2, no matter what
"proof" accompanies it.

Joint work with Madhu Sudan.