# Shorter and Simpler PCPs

 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)