TY - GEN

T1 - Public vs private coin in bounded-round information

AU - Braverman, Mark

AU - Garg, Ankit

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=84904163422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904163422&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-43948-7_42

DO - 10.1007/978-3-662-43948-7_42

M3 - Conference contribution

AN - SCOPUS:84904163422

SN - 9783662439470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 502

EP - 513

BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings

PB - Springer Verlag

T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

Y2 - 8 July 2014 through 11 July 2014

ER -