Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-130 | 17th January 2014 00:27

Public vs private coin in bounded-round information

RSS-Feed




Revision #1
Authors: Mark Braverman, Ankit Garg
Accepted on: 17th January 2014 00:27
Downloads: 977
Keywords: 


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 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+\log I + O(1)$ bits of information. Moreover, we give an example where this bound is tight: at least $I+\log I-O(1)$ bits are necessary in some cases. Our example also shows that the one-round compression construction of Harsha et al. [HJMR07] cannot be improved.



Changes to previous version:

Fixed a minor bug. Thanks to Anup Rao and Makrand Sinha for pointing it out. Also added some open problems.


Paper:

TR13-130 | 17th September 2013 16:54

Public vs private coin in bounded-round information





TR13-130
Authors: Mark Braverman, Ankit Garg
Publication: 17th September 2013 19:45
Downloads: 1339
Keywords: 


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 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+\log I + O(1)$ bits of information. Moreover, we give an example where this bound is tight: at least $I+\log I-O(1)$ bits are necessary in some cases. Our example also shows that the one-round compression construction of Harsha et al. [HJMR07] cannot be improved.



ISSN 1433-8092 | Imprint