{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T06:27:26Z","timestamp":1750746446221,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_56","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"648-658","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Communication Protocols for Deciding Edit Distance"],"prefix":"10.1007","author":[{"given":"Hossein","family":"Jowhari","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R.: The computational hardness of estimating edit distance [extended abstract]. In: FOCS, pp. 724\u2013734 (2007)","DOI":"10.1109\/FOCS.2007.60"},{"key":"56_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R., Onak, K.: Polylogarithmic approximation for edit distance and the asymmetric query complexity. In: FOCS, pp. 377\u2013386 (2010)","DOI":"10.1109\/FOCS.2010.43"},{"key":"56_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficiently. In: FOCS, pp. 550\u2013559 (2004)","DOI":"10.1109\/FOCS.2004.14"},{"key":"56_CR4","doi-asserted-by":"crossref","unstructured":"Batu, T., Erg\u00fcn, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A sublinear algorithm for weakly approximating edit distance. In: STOC, pp. 316\u2013324 (2003)","DOI":"10.1145\/780587.780590"},{"key":"56_CR5","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Transactions on Algorithms\u00a03(1) (2007)","DOI":"10.1145\/1219944.1219947"},{"key":"56_CR6","unstructured":"Cormode, G., Paterson, M., Sahinalp, S.C., Vishkin, U.: Communication complexity of document exchange. In: SODA, pp. 197\u2013206 (2000)"},{"key":"56_CR7","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Indyk, P.: Sparse recovery using sparse matrices. Proceedings of IEEE (2010)","DOI":"10.1109\/JPROC.2010.2045092"},{"key":"56_CR8","unstructured":"Gopalan, P., Jayram, T.S., Krauthgamer, R., Kumar, R.: Estimating the sortedness of a data stream. In: SODA, pp. 318\u2013327 (2007)"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"Irmak, U., Mihaylov, S., Suel, T.: Improved single-round protocols for remote file synchronization. In: INFOCOM, pp. 1665\u20131676 (2005)","DOI":"10.1109\/INFCOM.2005.1498448"},{"issue":"2","key":"56_CR10","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM Journal of Research and Development"},{"key":"56_CR11","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"2","key":"56_CR12","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27","author":"G.M. Landau","year":"1998","unstructured":"Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput.\u00a027(2), 557\u2013582 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"56_CR13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci.\u00a020(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"56_CR14","doi-asserted-by":"crossref","unstructured":"Orlitsky, A.: Interactive communication: Balanced distributions, correlated files, and average-case complexity. In: FOCS, pp. 228\u2013238 (1991)","DOI":"10.1109\/SFCS.1991.185373"},{"key":"56_CR15","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y.: Low distortion embeddings for edit distance. J. ACM\u00a054(5) (2007)","DOI":"10.1145\/1284320.1284322"},{"key":"56_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-73437-6_19","volume-title":"Combinatorial Pattern Matching","author":"E. Porat","year":"2007","unstructured":"Porat, E., Lipsky, O.: Improved Sketching of Hamming Distance with Error Correcting. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 173\u2013182. Springer, Heidelberg (2007)"},{"key":"56_CR17","unstructured":"Sun, X., Woodruff, D.P.: The communication and streaming complexity of computing the longest common and increasing subsequences. In: SODA, pp. 336\u2013345 (2007)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T11:34:22Z","timestamp":1744025662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}