BARC Talk by Noga Ron-Zewi: Highly-efficient local proofs

Highly-efficient local proofs

Abstract:

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. 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 cryptographic applications, 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), and moreover, the prover complexity overhead can be made constant.  

The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code.

Based on Joint work with Ron Rothblum