Revised: January 15, 2022
Published: June 7, 2022
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).