On doubly-efficient interactive proof systems

Webpage by Oded Goldreich

An interactive proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time. Such proof systems, introduced by Goldwasser, Kalai, and Rothblum (JACM, 2015), make the benefits of interactive proof system available to real-life agents who are restricted to polynomial-time computation.

This web-page provides access to a survey of the area as well as to the three texts that were used as a basis for this survey (i.e., a research paper co-authored by Guy Rothblum and expositions of two prior results, which are based on oral presentations by Guy of these results).

The survey

We survey the main two constructions of doubly-efficient interactive proof system: the system for sets having (uniform) bounded-depth circuits (due to Goldwasser, Kalai and Rothblum (JACM, 2015)), and the system for sets that are recognized in polynomial-time and small space (due to Reingold, Rothblum, and Rothblum (STOC, 2016)). Our presentation of the first construction is quite complete (except for some technical details), but for the second construction we only provide an overview. In addition, we present simpler constructions of doubly-efficient interactive proof system for ``locally characterizable'' sets like $t$-noCLIQUE (due to Goldreich and Rothblum (ECCC, 2017)).

See slides for a short talk and photos of a board talk (Parts 1 and 2).

The aforementioned prior work and expositions

This part of the web-page provides access to simple constructions of doubly-efficient interactive proof systems (joint work with Guy Rothblum) as well as to expositions of two prior results (see below).

Back to either Oded Goldreich's homepage or general list of papers.