School of Technology and Computer Science Seminars
Public vs Private-Coin Information Complexity
by Mr. Ankit Garg (Princeton University, USA)
Tuesday, September 10, 2013
from
to
(Asia/Kolkata)
at Colaba Campus ( AG-80 )
at Colaba Campus ( AG-80 )
Description |
We study the relation between public and private-coin information complexity. Improving a recent result by Brody et al., we prove that a one-round private-coin protocol with information cost I can be simulated by a one-round public-coin protocol with information cost \le I + \log(I) + O(1). This question is connected to the question of compression of interactive protocols and direct sum for communication complexity. We also give a lower bound. We exhibit a one-round private-coin protocol with information cost ~ n/2 - \log(n) which cannot be simulated by any public-coin protocol with information cost n/2 - O(1). This example also explains an additive \log factor incurred in the study of communication complexity of correlations by Harsha et al. |