Tata Institute of Fundamental Research

Public vs Private-Coin Information Complexity

Seminar
Speaker: Mr. Ankit Garg (Princeton University Department of Computer Science 35, Olden Street Princeton, NJ 08544 United States of America  )
Organiser: Arkadev Chattopadhyay
Date: Tuesday, 10 Sep 2013, 14:30 to 15:30
Venue: AG-80

(Scan to add to calendar)
Abstract:  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 can be simulated by a one-round public-coin protocol with information cost ≤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 \tilda 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.