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

Saturday, 10 Dec 2011, 11:00 to 12:00
A-212 (STCS Seminar Room)
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(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.

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)