Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-062 | 22nd March 2014 17:16

On the role of private coins in unbounded-round Information Complexity

RSS-Feed




TR14-062
Authors: Alexander Kozachinsky
Publication: 22nd April 2014 17:10
Downloads: 589
Keywords: 


Abstract:

We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication whereas previous results in this area dealt with one-way protocols. As an application it gives an undirect way to prove a best-known compression theorem in Information Complexity.



ISSN 1433-8092 | Imprint