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

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.

- First version posted: July 2017.
- Revisions: March 2018, March 2021.

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).
- Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems. The 2nd part of this work presents a direct and simple interactive proof system for counting $t$-cliques in $n$-vertex graphs. The proof system uses $t-2$ rounds, the verifier runs in ${\widetilde O}(t^2n^2)$-time, and the prover can be implemented in ${\widetilde O}(t^{O(1)}\cdot n^2)$-time when given oracle access to counting $(t-1)$-cliques in ${\widetilde O}(t^{O(1)}\cdot n)$-vertex graphs.
- 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.