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

We show lower bounds of $Omega(sqrt{n})$ on the randomized 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(dlog 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.

It is a small paper. I will try to present some additional results proofs of which is not included in this paper. I will need 40 mins to complete the presentation.

(Author: Rahul Jain, Hartmut Klauck, Shengyu Zhang)