Depth-independent lower bounds on the communication complexity of read-once Boolean formulas

Abstract

We show lower bounds of 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(dlogd)) 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. © 2010 Springer-Verlag Berlin Heidelberg.