Welcome to the resource topic for 2024/952
Title:
Communication Complexity vs Randomness Complexity in Interactive Proofs
Authors: Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran
Abstract: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 bits into another one for the same problem with the additional property that the verifier’s communication is bounded by O(I\cdot \rho). Importantly, this is done with a minor, logarithmic, increase in the communication from the prover to the verifier and while preserving the randomness complexity. Along the way, we introduce a new compression game between computationally-bounded compressor and computationally-unbounded decompressor and a new notion of conditioned efficient distributions that may be of independent interest. Our solutions are based on a combination of perfect hashing and pseudorandom generators.
ePrint: https://eprint.iacr.org/2024/952
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .