Skip to main content

Public vs Private Coin in Bounded-Round Information

Author(s): Braverman, Mark; Garg, Ankit

To refer to this page use:
Abstract: We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We give an example of a (randomized) message which can be transmitted while revealing only I bits of information using private randomness, but requires Alice to reveal I + logI − O(1) bits of information if only public coins are allowed. This gives the first example of an ω(1) additive separation between these two models. Our example also shows that the one-round compression construction of Harsha et al. [HJMR07] cannot be improved. Moreover, we show that our example is tight up to an additive O(1) factor: We show that if using private randomness a message can be transmitted while revealing I bits of information, the transmission can be simulated without private coins using I + logI + O(1) bits of information. This improves over an earlier result by Brody et al. [BBK+12].
Publication Date: 2014
Citation: Braverman, Mark, and Ankit Garg. "Public vs Private Coin in Bounded-Round Information." Automata, Languages, and Programming (2014): pp. 502-513. doi:10.1007/978-3-662-43948-7_42
DOI: 10.1007/978-3-662-43948-7_42
Pages: 502 - 513
Type of Material: Conference Article
Series/Report no.: Lecture Notes in Computer Science;
Journal/Proceeding Title: Automata, Languages, and Programming
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.