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 four texts that were used as a basis for this survey (i.e., two research papers co-authored by Guy Rothblum and expositions of two prior results, which are based on oral presentations by Guy of these results).

The survey

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.

We survey some of the known results regarding doubly-efficient interactive proof system. We start by presenting two simple constructions for no-$t$-CLIQUE (due to Goldreich and Rothblum (ECCC, TR17-018 and TR18-046)), where the first construction offers the benefit of being generalized to any ``locally characterizable'' set, and the second construction offers the benefit of preserving the combinatorial flavor of the problem. We then turn to two more general constructions of doubly-efficient interactive proof system: the proof system for sets having (uniform) bounded-depth circuits (due to Goldwasser, Kalai and Rothblum (JACM, 2015)), and the proof system for sets that are recognized in polynomial-time and small space (due to Reingold, Rothblum, and Rothblum (STOC, 2016)). Our presentation of the GKR construction is quite complete (and is somewhat different from the original presentation), but for the RRR construction we only provide an overview.

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.