Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-102 | 9th June 2017 14:42

Overview of the doubly-efficient interactive proof systems of RRR

RSS-Feed




TR17-102
Authors: Oded Goldreich
Publication: 9th June 2017 14:43
Downloads: 163
Keywords: 


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



ISSN 1433-8092 | Imprint