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 $\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 $\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.
| 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 $\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 $\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.
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.