## Overview of the doubly-efficient interactive proof systems of RRR

#### Webpage for an exposition by Oded Goldreich

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