Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR15-057 | 14th December 2017 01:29

Simplified Separation of Information and Communication

RSS-Feed




Revision #3
Authors: Anup Rao, Makrand Sinha
Accepted on: 14th December 2017 01:29
Downloads: 115
Keywords: 


Abstract:

We give an example of a boolean function whose information complexity is exponentially smaller than its communication complexity. This was first proven recently by Ganor, Kol and Raz (J. ACM 2016) and our work gives a simpler proof of the same result. In the course of this simplification, we make several new contributions: we introduce a new communication lower bound technique, the notion of a \emph{fooling distribution}, which allows us to separate information and communication complexity, and we also give a more direct proof for the information complexity upper bound. We also prove a generalization of Shearer's Lemma that may be of independent interest.



Changes to previous version:

More details and examples added.


Revision #2 to TR15-057 | 14th April 2015 03:12

Simplified Separation of Information and Communication





Revision #2
Authors: Anup Rao, Makrand Sinha
Accepted on: 14th April 2015 03:12
Downloads: 636
Keywords: 


Abstract:

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).



Changes to previous version:

Fixed a typo concerning the indices in the proof.


Revision #1 to TR15-057 | 13th April 2015 17:46

Simplified Separation of Information and Communication





Revision #1
Authors: Anup Rao, Makrand Sinha
Accepted on: 13th April 2015 17:46
Downloads: 474
Keywords: 


Abstract:

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).



Changes to previous version:

Fixed an error in the previous definition of the distribution.


Paper:

TR15-057 | 13th April 2015 08:15

Simplified Separation of Information and Communication





TR15-057
Authors: Anup Rao, Makrand Sinha
Publication: 13th April 2015 09:21
Downloads: 1037
Keywords: 


Abstract:

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).



ISSN 1433-8092 | Imprint