Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
REPORTS > KEYWORD > COMMUNICATION COMPLEXITY, INFORMATION COMPLEXITY:
Reports tagged with Communication Complexity, Information Complexity:
TR15-057 | 13th April 2015
Anup Rao, Makrand Sinha

Simplified Separation of Information and Communication

 Revisions: 3

We give an example of a boolean function whose information complexity is exponentially
smaller than its communication complexity. Our result simplifies recent work of Ganor, Kol and
Raz (FOCS'14, STOC'15).

more >>>


ISSN 1433-8092 | Imprint