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]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: complexity theory, interactive proofs
Categories: complexity, interactive proofs, randomness, RANDOM, RANDOM 2018 special issue
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).