1. ScholarBank@NUS
  2. 1. Staff
  3. Staff Publications
Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-14031-0_8
DC FieldValue
dc.titleDepth-independent lower bounds on the communication complexity of read-once Boolean formulas
dc.contributor.authorJain, R.
dc.contributor.authorKlauck, H.
dc.contributor.authorZhang, S.
dc.date.accessioned2013-07-04T08:20:59Z
dc.date.available2013-07-04T08:20:59Z
dc.date.issued2010
dc.identifier.citationJain, 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. <a href="https://doi.org/10.1007/978-3-642-14031-0_8" target="_blank">https://doi.org/10.1007/978-3-642-14031-0_8</a>
dc.identifier.isbn3642140300
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/41159
dc.description.abstractWe 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/978-3-642-14031-0_8
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1007/978-3-642-14031-0_8
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume6196 LNCS
dc.description.page54-59
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


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