pdf icon
Volume 18 (2022) Article 13 pp. 1-65
RANDOM 2018 Special Issue
Round Complexity Versus Randomness Complexity in Interactive Proofs
Received: September 19, 2018
Revised: January 15, 2022
Published: June 7, 2022
Download article from ToC site:
[PDF (743K)] [PS (4940K)] [Source ZIP]
Keywords: complexity theory, interactive proofs
ACM Classification: F.1.3
AMS Classification: 68Q10, 68Q15, 68Q87

Abstract: [Plain Text Version]

Consider an interactive proof system for some set $S$ that has randomness complexity $r(n)$ for instances of length $n$, and arbitrary round complexity. We show a public coin interactive proof system for $S$ of round complexity $O(r(n)/\log r(n))$. Furthermore, the randomness complexity is preserved up to a constant factor, and the resulting interactive proof system has perfect completeness.


An extended abstract of this paper appeared in the Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM'18).