{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:53:29Z","timestamp":1725558809826},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642140303"},{"type":"electronic","value":"9783642140310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14031-0_8","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T09:50:06Z","timestamp":1277718606000},"page":"54-59","source":"Crossref","is-referenced-by-count":2,"title":["Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Jain","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hartmut","family":"Klauck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengyu","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Ambainis, A., Childs, A., Reichardt, B., Spalek, R., Zhang, S.: Any AND-OR formula of size n can be evaluated in time n 1\/2\u2009+\u2009o(1) on a quantum computer. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 363\u2013372 (2007)","key":"8_CR1","DOI":"10.1109\/FOCS.2007.57"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pp. 63\u201368 (1998)","key":"8_CR2","DOI":"10.1145\/276698.276713"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-49208-9_4","volume-title":"Quantum Computing and Quantum Communications","author":"R. Cleve","year":"1999","unstructured":"Cleve, R., van Dam, W., Nielsen, M., Tapp, A.: Quantum entanglement and the communication complexity of the inner product function. In: Williams, C.P. (ed.) QCQC 1998. LNCS, vol.\u00a01509, pp. 61\u201374. Springer, Heidelberg (1999)"},{"doi-asserted-by":"crossref","unstructured":"Heiman, R., Wigderson, A.: Randomized vs. deterministic decision tree complexity for read-once boolean functions. In: Proceedings of the 6th Structures in Complexity Theory Conference, pp. 172\u2013179 (1991)","key":"8_CR4","DOI":"10.1109\/SCT.1991.160258"},{"doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Kopparty, S., Raghavendra, P.: On the communication complexity of read-once ac0 formula. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pp. 329\u2013340 (2009)","key":"8_CR5","DOI":"10.1109\/CCC.2009.39"},{"doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Kumar, R., Sivakumar, D.: Two applications of information complexity. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (STOC), pp. 673\u2013682 (2003)","key":"8_CR6","DOI":"10.1145\/780542.780640"},{"key":"8_CR7","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics\u00a05(4), 545\u2013557 (1992); Earlier version in Structures \u201987","journal-title":"SIAM Journal on Discrete Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Leonardos, N., Saks, M.: Lower bounds on the randomized communication complexity of read-once functions. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pp. 341\u2013350 (2009)","key":"8_CR9","DOI":"10.1109\/CCC.2009.32"},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A. Razborov","year":"1992","unstructured":"Razborov, A.: On the distributional complexity of disjointness. Theoretical Computer Science\u00a0106(2), 385\u2013390 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"8_CR11","first-page":"159","volume":"67","author":"A. Razborov","year":"2003","unstructured":"Razborov, A.: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, mathematics\u00a067(1), 159\u2013176 (2003), quant-ph\/0204025","journal-title":"Izvestiya of the Russian Academy of Science, mathematics"},{"issue":"5-6","key":"8_CR12","doi-asserted-by":"crossref","first-page":"435","DOI":"10.26421\/QIC10.5-6-5","volume":"10","author":"A. Sherstov","year":"2010","unstructured":"Sherstov, A.: On quantum-classical equivalence for composed communication problems. Quantum Information and Computation\u00a010(5-6), 435\u2013455 (2010)","journal-title":"Quantum Information and Computation"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"Snir, M.: Lower bounds for probabilistic linear decision trees. Theoretical Computer Science\u00a038, 69\u201382 (1985)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, pp. 29\u201338 (1986)","key":"8_CR14","DOI":"10.1109\/SFCS.1986.44"},{"doi-asserted-by":"crossref","unstructured":"Zhang, S.: On the tightness of the Buhrman-Cleve-Wigderson simulation. In: Proceedings of the 20th International Symposium on Algorithms and Computation, pp. 434\u2013440 (2009)","key":"8_CR15","DOI":"10.1007\/978-3-642-10631-6_45"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14031-0_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T07:44:15Z","timestamp":1635579855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14031-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642140303","9783642140310"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14031-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}