Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
Jain, R. Klauck, H. Zhang, S.
Klauck, H.
Zhang, S.
Citations
Altmetric:
Alternative Title
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.
Keywords
Source Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher
Series/Report No.
Collections
Rights
Date
2010
DOI
10.1007/978-3-642-14031-0_8
Type
Conference Paper