Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with FFT:
TR04-060 | 22nd July 2004
Eli Ben-Sasson, Madhu Sudan

Simple PCPs with Poly-log Rate and Query Complexity

We give constructions of PCPs of length n*polylog(n) (with respect
to circuits of size n) that can be verified by making polylog(n)
queries to bits of the proof. These PCPs are not only shorter than
previous ones, but also simpler. Our (only) building blocks are
Reed-Solomon codes and the bivariate ... more >>>

ISSN 1433-8092 | Imprint