Tata Institute of Fundamental Research
Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas
Seminar
Speaker:
Sagnik Mukhopadhyay
Date:
Saturday, 10 Dec 2011, 11:00 to 12:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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)
| Speaker: | Sagnik Mukhopadhyay |
| Date: | Saturday, 10 Dec 2011, 11:00 to 12:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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)
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)