Overview of the doubly-efficient interactive proof systems of RRR

Abstract

We provide 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 ${\widetilde O}(n)$.

Material available on-line

• First version posted: June 2017.
• Revisions: none yet.

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