{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:50:55Z","timestamp":1787500255058,"version":"build-2736575974"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T00:00:00Z","timestamp":1435276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-01-05413, CCR-02-08005, CCF 14-22569, CNS-1010789,"],"award-info":[{"award-number":["CCR-01-05413, CCR-02-08005, CCF 14-22569, CNS-1010789,"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,7,9]]},"abstract":"<jats:p>\n                    Alice and Bob want to know if two strings of length\n                    <jats:italic>n<\/jats:italic>\n                    are almost equal. That is, do the strings differ on\n                    <jats:italic>at most<\/jats:italic>\n                    <jats:italic>a<\/jats:italic>\n                    bits? Let 0 \u2a7d\n                    <jats:italic>a<\/jats:italic>\n                    \u2a7d\n                    <jats:italic>n<\/jats:italic>\n                    \u2212 1. We show (1) any deterministic protocol\u2014as well as any error-free quantum protocol (\n                    <jats:italic>C<\/jats:italic>\n                    * version)\u2014for this problem requires at least\n                    <jats:italic>n<\/jats:italic>\n                    \u2212 2 bits of communication, and (2) a lower bound of\n                    <jats:italic>n<\/jats:italic>\n                    \/2 \u2212 1 for error-free\n                    <jats:italic>Q<\/jats:italic>\n                    * quantum protocols. We also show the same results for determining if two strings differ in\n                    <jats:italic>exactly<\/jats:italic>\n                    <jats:italic>a<\/jats:italic>\n                    bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.\n                  <\/jats:p>","DOI":"10.1145\/2698587","type":"journal-article","created":{"date-parts":[[2015,6,29]],"date-time":"2015-06-29T14:10:42Z","timestamp":1435587042000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems"],"prefix":"10.1145","volume":"7","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Gasarch","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrey","family":"Utis","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,6,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.262591"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.69.2881"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 16th IEEE Conference on Complexity Theory. IEEE Computer Society Press","author":"Buhrman H.","year":"2001","unstructured":"H. Buhrman and R. de Wolf . 2001 . Communication complexity lower bounds by polynomials . In Proceedings of the 16th IEEE Conference on Complexity Theory. IEEE Computer Society Press , Los Alamitos, CA, 120--130. H. Buhrman and R. de Wolf. 2001. Communication complexity lower bounds by polynomials. In Proceedings of the 16th IEEE Conference on Complexity Theory. IEEE Computer Society Press, Los Alamitos, CA, 120--130."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(90)90072-X"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the11th Symposium on Discrete Algorithms (SODA\u201900)","author":"Cormode G.","unstructured":"G. Cormode , M. Paterson , S. Sahinalp , and U. Vishkin . 2000. Communication complexity of document exchange . In Proceedings of the11th Symposium on Discrete Algorithms (SODA\u201900) . ACM-SIAM, New York, NY, 197--206. G. Cormode, M. Paterson, S. Sahinalp, and U. Vishkin. 2000. Communication complexity of document exchange. In Proceedings of the11th Symposium on Discrete Algorithms (SODA\u201900). ACM-SIAM, New York, NY, 197--206."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00377-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"J.\n      Feigenbaum Y.\n      Ishai T.\n      Malkin K.\n      Nissim M.\n      Strauss and \n      R.\n      Wright\n  . \n  2001\n  . Secure multiparty computation of approximations. In Proceedings of the 28th International Colloquium on Automata Languages and Programming (ICALP\u201901) Lecture Notes in Computer Science Vol. \n  2076\n  . \n  Springer-Verlag New York 927--938.   J. Feigenbaum Y. Ishai T. Malkin K. Nissim M. Strauss and R. Wright. 2001. Secure multiparty computation of approximations. In Proceedings of the 28th International Colloquium on Automata Languages and Programming (ICALP\u201901) Lecture Notes in Computer Science Vol. 2076. Springer-Verlag New York 927--938.","DOI":"10.1007\/3-540-48224-5_75"},{"key":"e_1_2_1_8_1","unstructured":"D. Gavinsky J. Kempe and R. de Wolf. 2004. Quantum communication cannot simulate a public coin. (2004). arxiv.org\/abs\/quant-ph\/0411051.  D. Gavinsky J. Kempe and R. de Wolf. 2004. Quantum communication cannot simulate a public coin. (2004). arxiv.org\/abs\/quant-ph\/0411051."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.39"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.01.014"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press Cambridge England.   E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press Cambridge England.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802208"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.88489"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406043"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215065"},{"key":"e_1_2_1_16_1","volume-title":"Orthogonal Polynomials","author":"Szego G.","unstructured":"G. Szego . 1975. Orthogonal Polynomials ( 4 th ed.). Colloquium Publications of the American Math Society, Vol. 23 . American Math Society , Providence. G. Szego. 1975. Orthogonal Polynomials (4th ed.). Colloquium Publications of the American Math Society, Vol. 23. American Math Society, Providence.","edition":"4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780554"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2698587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2698587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:12:12Z","timestamp":1750212732000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2698587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,26]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7,9]]}},"alternative-id":["10.1145\/2698587"],"URL":"https:\/\/doi.org\/10.1145\/2698587","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,26]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}