Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kaartik Bhushan:

TR24-105 | 13th June 2024
Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran

Communication Complexity vs Randomness Complexity in Interactive Proofs

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random ... more >>>

ISSN 1433-8092 | Imprint