Authors
Oded Goldreich
Publication date
2017/6/9
Journal
Electronic Colloquium on Computational Complexity (ECCC)
Volume
24
Pages
102
Description
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)≤ n0. 499, has a constant-round interactive proof system in which the prover runs polynomial time and the verifier runs in time
Total citations
Scholar articles
O Goldreich - Electronic Colloquium on Computational Complexity …, 2017