Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
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.
All Author(s) ListJain R., Klauck H., Zhang S.
Name of Conference16th Annual International Computing and Combinatorics Conference, COCOON 2010
Start Date of Conference19/07/2010
End Date of Conference21/07/2010
Place of ConferenceNha Trang
Country/Region of ConferenceVietnam
Detailed descriptionTo ORKTS: Authors listed alphabetically according to the convention of the community of theoretical computer science.
Volume Number6196 LNCS
PublisherSpringer Verlag
Place of PublicationGermany
Pages54 - 59
LanguagesEnglish-United Kingdom

Last updated on 2021-28-11 at 23:32