{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:59Z","timestamp":1725514439816},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_28","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"306-317","source":"Crossref","is-referenced-by-count":3,"title":["Quantum Multiparty Communication Complexity and Circuit Lower Bounds"],"prefix":"10.1007","author":[{"given":"Iordanis","family":"Kerenidis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2063","key":"28_CR1","doi-asserted-by":"publisher","first-page":"3473","DOI":"10.1098\/rspa.2005.1546","volume":"461","author":"S. Aaronson","year":"2063","unstructured":"Aaronson, S.: Quantum Computing, Postselection, and Probabilistic Polynomial-Time. Proceedings of the Royal Society A\u00a0461(2063), 3473\u20133482 (2063)","journal-title":"Proceedings of the Royal Society A"},{"key":"28_CR2","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP \u2229 coNP. In: Proc. 45th IEEE FOCS (2004)"},{"issue":"2","key":"28_CR3","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. Journal of Computer and System Sciences\u00a045(2), 204\u2013232 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Beigel, R., Tarui, J.: On ACC. Computational Complexity (1994)","DOI":"10.1007\/BF01263423"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kerenidis, I.: Exponential Separation of Quantum and Classical One-Way Communication Complexity. In: Proceedings of 36th ACM STOC (2004)","DOI":"10.1145\/1007352.1007379"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Buhrman, H., et al.: Quantum fingerprinting. Physical Review Letters\u00a087(16) (2001)","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: Proceedings of the 15th annual ACM STOC (1983)","DOI":"10.1145\/800061.808737"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Chung, F.: Quasi-random classes of hypergraphs. Random Structures and Algorithms (1990)","DOI":"10.1002\/rsa.3240010401"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Grolmusz, V.: The BNS Lower Bound for Multi-Party Protocols is Nearly Optimal. Information and Computation (1994)","DOI":"10.1006\/inco.1994.1051"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01272517","volume":"1","author":"J. Hastad","year":"1991","unstructured":"Hastad, J., Goldmann, M.: On the power of small-depth threshold circuits. Computational Complexity\u00a01, 113\u2013129 (1991)","journal-title":"Computational Complexity"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument. In: Proceedings of the 15th annual ACM STOC (2003)","DOI":"10.1145\/780542.780560"},{"key":"28_CR12","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)"},{"key":"28_CR13","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"2000","unstructured":"Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"issue":"2","key":"28_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/PL00001602","volume":"9","author":"R. Raz","year":"2000","unstructured":"Raz, R.: The BNS-Chung Criterion for multi-party communication complexity. Journal of Computational Complexity\u00a09(2), 113\u2013122 (2000)","journal-title":"Journal of Computational Complexity"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Raz, R.: Exponential separation of quantum and classical communication complexity. In: Proceedings of 31st ACM STOC (1999)","DOI":"10.1145\/301250.301343"},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1424","DOI":"10.1007\/11523468_115","volume-title":"Automata, Languages and Programming","author":"S. Wehner","year":"2005","unstructured":"Wehner, S., de Wolf, R.: Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1424\u20131436. Springer, Heidelberg (2005)"},{"key":"28_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/11786986_7","volume-title":"Automata, Languages and Programming","author":"R. Wolf de","year":"2006","unstructured":"de Wolf, R.: Lower Bounds on Matrix Rigidity via a Quantum Argument. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 62\u201371. Springer, Heidelberg (2006)"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: On ACC and threshold circuits. In: Proc. 31st Ann. IEEE FOCS (1990)","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:09Z","timestamp":1619516289000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_28","relation":{},"subject":[]}}