Theory of Computing
-------------------
Title     : Round Complexity Versus Randomness Complexity in Interactive Proofs
Authors   : Maya Leshkowitz
Volume    : 18
Number    : 13
Pages     : 1-65
URL       : https://theoryofcomputing.org/articles/v018a013

Abstract
--------

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