We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae.
A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... more >>>
Let \mathcal{M} be a bridgeless matroid on ground set \{1,\ldots, n\} and f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\} be the indicator function of its independent sets. A folklore fact is that f_\mathcal{M} is ``evasive," i.e., D(f_\mathcal{M}) = n where D(f) denotes the deterministic decision tree complexity of f. Here we prove ... more >>>