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).

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)).

- First version posted: July 2017.
- Revisions: none yet.

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).

- Simple doubly-efficient interactive proof systems for locally-characterizable sets. Presents direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity. Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM. These constructions are generalized to a generic construction for a natural class that contains both problems and is in NC (and also in SC).
- On the doubly-efficient interactive proof systems of GKR. Presents a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015). These proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in the proof system is linearly related to the depth of the circuit).
- Overview of the doubly-efficient interactive proof systems of RRR. Provides an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016). Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system in which the prover runs polynomial time and the verifier runs in time $\tildeO(n)$.

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