| COMPUTER SCIENCE/DISCRETE MATH SEMINAR, I | |
| Topic: | Shorter and Simpler PCPs |
| Speaker: | Madhu Sudan |
| Affiliation: | MIT |
| Date: | Monday, January 24 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
We present new PCPs for NP-complete languages. The PCPs are only n poly log n bits long, when proving satisfiability of formulae of length n. However, the probabilistic verifier needs to query poly log n bits of the proof to verify it.
In contrast to most earlier PCP constructions, these PCPs are based on the properties of (relatively high-degree)
*univariate* polynomials. Most of the earlier steps in PCPs get simplified in our setting by our ability to work with such high-degree polynomials. The technical crux of the construction is a ``low-degree test/proof'' for univariate polynomials that is verifiable with only polylogarithmically many queries (relative to the degree of the polynomial being tested) into the proof.
Joint work with Eli Ben-Sasson (Toyota Institute of Technology)