Please use this identifier to cite or link to this item:
https://doi.org/10.1007/978-3-642-14031-0_8
Title: | Depth-independent lower bounds on the communication complexity of read-once Boolean formulas | Authors: | Jain, R. Klauck, H. Zhang, S. |
Issue Date: | 2010 | Citation: | Jain, R.,Klauck, H.,Zhang, S. (2010). Depth-independent lower bounds on the communication complexity of read-once Boolean formulas. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6196 LNCS : 54-59. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-14031-0_8 | 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. | Source Title: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | URI: | http://scholarbank.nus.edu.sg/handle/10635/41159 | ISBN: | 3642140300 | ISSN: | 03029743 | DOI: | 10.1007/978-3-642-14031-0_8 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
SCOPUSTM
Citations
5
checked on Nov 28, 2019
Page view(s)
94
checked on Dec 2, 2019
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.