Paper 2024/952
Communication Complexity vs Randomness Complexity in Interactive Proofs
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
Note: Preliminary version appears in ITC'24.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. ITC 2024.
- Keywords
- interactive proofs
- Contact author(s)
-
benny applebaum @ gmail com
kbhushan @ cse iitb ac in
mp @ cse iitb ac in - History
- 2024-06-14: approved
- 2024-06-13: received
- See all versions
- Short URL
- https://ia.cr/2024/952
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/952, author = {Benny Applebaum and Kaartik Bhushan and Manoj Prabhakaran}, title = {Communication Complexity vs Randomness Complexity in Interactive Proofs}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/952}, year = {2024}, url = {https://eprint.iacr.org/2024/952} }