Abstract:

A proof is said to be probabilistically checkable if it can be
verified (super-efficiently) by a probabilistic verifier who
reads a tiny number of bits from the proof (and accepts valid
proofs, while rejecting any claimed proof of invalid theorems
with high probability). A decade old result showed that standard
proofs can be converted into probabilistically checkable proofs
(PCPs) with only a polynomial blowup in the length of the proof.

In principle, such a result means that every mathematical proof
can be written in a PCP format so as to make verification easy.
For practical applications, one would hope that this would allow
us to maintain transcripts of executions of computer programs
that are very easy to audit. Yet, PCPs have never entered the
realm of such usage. Their use, so far, has been mostly limited
to proving negative results about combinatorial optimization.

Part of the reason for this lack of common use has been that
current constructions of PCPs (1) are very complex, and (2)
stretch the size of the proof by unreasonably large factors. In
this talk we describe a new construction of PCPs. These
constructions lead to shorter PCPs that are arguably simpler
than previous ones. In this talk, we will describe the main
steps in this construction. The talk will be self-contained.

[Joint work with Madhu Sudan.]