{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:12Z","timestamp":1725474972250},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_63","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T05:57:35Z","timestamp":1164779855000},"page":"628-637","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Gasarch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrey","family":"Utis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"63_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1109\/71.262591","volume":"5","author":"K. Abdel-Ghaffar","year":"1994","unstructured":"Abdel-Ghaffar, K., Ababdi, A.E.: An optimal strategy for comparing file copies. IEEE Transactions on Parallel and Distributed Systems\u00a05, 87\u201393 (1994)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"63_CR2","volume-title":"Proc. of the 16th IEEE Conf. on Complexity Theory","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., de Wolf, R.: Communication complexity lower bounds by polynomials. In: Proc. of the 16th IEEE Conf. on Complexity Theory, IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"63_CR3","unstructured":"Cormode, G., Paterson, M., Sahinalp, S., Vishkin, U.: Communication complexity of document exchange. In: Proc. of the 11th ACM Symp. on Discrete Algorithms, pp. 197\u2013206 (2000)"},{"key":"63_CR4","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00377-8","volume":"12","author":"R. Wolf de","year":"2002","unstructured":"de Wolf, R.: Quantum communication and complexity. Theoretical Comput. Sci.\u00a012, 337\u2013353 (2002)","journal-title":"Theoretical Comput. Sci."},{"key":"63_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1007\/3-540-48224-5_75","volume-title":"Automata, Languages and Programming","author":"J. Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M., Wright, R.: Secure multiparty computation of approximations. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 927\u2013938. Springer, Heidelberg (2001)"},{"key":"63_CR6","unstructured":"Gavinsky, D., Kempe, J., de Wolf, R.: Quantum communication cannot simulate a public coin (2004), arxiv.org\/abs\/quant-ph\/0411051"},{"key":"63_CR7","unstructured":"Huang, W., Shi, Y., Zhang, S., Zhu, Y.: The communication complexity of the Hamming distance problem, arxiv.org\/abs\/quant-ph\/0509181"},{"key":"63_CR8","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Lower Bounds for Quantum Communication Complexity. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 288\u2013297 (2001)","DOI":"10.1109\/SFCS.2001.959903"},{"key":"63_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1006\/jcta.1996.0038","volume":"74","author":"I. Krasikov","year":"1996","unstructured":"Krasikov, I., Litsyn, S.: On integral zeros of Krawtchouk polynomials. J.\u00a0Comb.\u00a0Theory Ser.\u00a0A\u00a074, 71\u201399 (1996)","journal-title":"J.\u00a0Comb.\u00a0Theory Ser.\u00a0A"},{"key":"63_CR10","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"63_CR11","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E.: Las Vegas is better than determinism for VLSI and distributed systems. In: Proc. of the 14th ACM Symp. on Theory of Computing, pp. 330\u2013337 (1982)","DOI":"10.1145\/800070.802208"},{"key":"63_CR12","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1109\/12.88489","volume":"40","author":"J. Metzner","year":"1991","unstructured":"Metzner, J.: Efficient replicated remote file comparison. IEEE Transactions on Computers\u00a040, 651\u2013659 (1991)","journal-title":"IEEE Transactions on Computers"},{"key":"63_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Inf. Process. Lett.\u00a039, 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"key":"63_CR14","doi-asserted-by":"crossref","unstructured":"Orlitsky, A.: Interactive communication: balanced distributions, correlated files, and average-case complexity. In: Proc. of the 32st IEEE Symp. on Found. of Comp. Sci., pp. 228\u2013238 (1991)","DOI":"10.1109\/SFCS.1991.185373"},{"key":"63_CR15","doi-asserted-by":"crossref","unstructured":"Pang, K., Gamal, A.E.: Communication complexity of computing the Hamming distance. SIAM Journal of Computing\u00a015 (1986)","DOI":"10.1137\/0215065"},{"key":"63_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01206318","volume":"5","author":"R. Raz","year":"1995","unstructured":"Raz, R.: Fourier analysis for probabilistic communication complexity. Journal of Computational Complexity\u00a05, 205\u2013221 (1995)","journal-title":"Journal of Computational Complexity"},{"key":"63_CR17","volume-title":"Generating functionology","author":"H. Wilf","year":"1994","unstructured":"Wilf, H.: Generating functionology. Academic Press, London (1994)"},{"key":"63_CR18","doi-asserted-by":"crossref","unstructured":"Yao, A.: On the power of quantum fingerprinting. In: Proc. of the 35th ACM Symp. on Theory of Computing, pp. 77\u201381 (2003)","DOI":"10.1145\/780542.780554"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_63.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:50:06Z","timestamp":1619509806000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11940128_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}