Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas

Abstract

We show lower bounds of $\Omega (\sqrt{n})$ and $\Omega (n^{1/4})$ on the randomized and quantum communication complexity, respectively, of all $n$-variable read-once Boolean formulas. Our results complement the recent lower bound of $\Omega (n/8^d)$ by Leonardos and Saks and $\Omega (n/2^{\Omega (d\log d)})$ by Jayram, Kopparty and Raghavendra for randomized communication complexity of read-once Boolean formulas with depth $d$. We obtain our result by "embedding" either the Disjointness problem or its complement in any given read-once Boolean formula.

5 pages