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

by Mr Sagnik Mukhopadhyay (School of Technology and Computer Science)

Saturday 10 Dec 2011, 11:00 → 12:00 Asia/Kolkata

A-212 (STCS Seminar Room) (Colaba Campus)

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)