ECCC-Report TR14-062https://eccc.weizmann.ac.il/report/2014/062Comments and Revisions published for TR14-062en-usTue, 22 Apr 2014 17:10:21 +0300
Paper TR14-062
| On the role of private coins in unbounded-round Information Complexity |
Alexander Kozachinsky
https://eccc.weizmann.ac.il/report/2014/062We 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.Tue, 22 Apr 2014 17:10:21 +0300https://eccc.weizmann.ac.il/report/2014/062