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

摘要

We show lower bounds of Ω({the square root of}n) and Ω(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 Ω(n/8~d) by Leonardos and Saks [LS09] and Ω(n/2~(O(d log d))) by Jayram, Kopparty and Raghavendra [JKR09] 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.