Jain, R.Klauck, H.Zhang, S.COMPUTER SCIENCE2013-07-042013-07-042010Jain, 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>364214030003029743https://scholarbank.nus.edu.sg/handle/10635/41159We 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.Conference PaperNOT_IN_WOS