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
Source: 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

4
checked on Dec 13, 2017

Page view(s)

52
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.