%0 Journal Article
%T Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
%A Rahul Jain
%A Hartmut Klauck
%A Shengyu Zhang
%J Computer Science
%D 2009
%I arXiv
%X 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.
%U http://arxiv.org/abs/0908.4453v1