Computer Science/Discrete Mathematics Seminar I

The celebrated PCP theorem from the 90's shows that any mathematical proof can be encoded in such a way that its correctness can be verified locally by reading only a tiny number of bits from the encoding. This foundational result has had a transformative effect on theoretical computer science with diverse applications in complexity theory and cryptography. 

A fundamental question that has drawn a great amount of interest is what is the minimal overhead in encoding that is needed to allow for such highly efficient local verification. While the original PCP theorem only guarantees a polynomial overhead, a beautiful line of work has culminated in remarkably short encodings with only a poly-logarithmic overhead. 

Motivated by recent practical implementations of such proof systems, we study a relatively new interactive variant of PCPs, called Interactive Oracle Proofs, and show that for this model the overhead in the encoding can be made arbitrarily small (approaching 1). Our proof leverages recent constructions of high-rate locally testable and decodable codes.  

Joint work with Ron Rothblum.