Name
Abstract | ||
|---|---|---|
We give an example of a Boolean function whose information complexity is exponentially smaller than its communication complexity. Such a separation was first demonstrated by Ganor, Kol and Raz (J. ACM 2016). We give 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 fooling distribution, which allows us to separate information and communication complexity, and we also give a more direct proof of the information complexity upper bound. We also prove a generalization of Shearer's Lemma that may be of independent interest. A version of Shearer's original lemma bounds the expected mutual information of a subset of random variables with another random variable, when the subset is chosen independently of all the random variables that are involved. Our generalization allows some dependence between the random subset and the random variables involved, and still gives us similar bounds with an appropriate error term. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4086/toc.2018.v014a020 | THEORY OF COMPUTING |
Keywords | DocType | Volume |
communication complexity,information complexity,fooling distribution,separation of complexity measures | Journal | 14 |
Issue | ISSN | Citations |
1 | 1557-2862 | 1 |
PageRank | References | Authors |
0.36 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anup Rao | 1 | 581 | 32.80 |
| Makrand Sinha | 2 | 12 | 3.67 |