{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T17:19:55Z","timestamp":1730222395674,"version":"3.28.0"},"reference-count":35,"publisher":"IEEE","license":[{"start":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:00:00Z","timestamp":1604188800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:00:00Z","timestamp":1604188800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:00:00Z","timestamp":1604188800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100003977","name":"ISF","doi-asserted-by":"publisher","award":["1278\/16,1926\/19"],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100001005","name":"BSF","doi-asserted-by":"publisher","award":["2018364"],"id":[{"id":"10.13039\/100001005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"ERC","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1652303 (NSF CAREER),1934846 (NSF HDR TRIPODS),1909046"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1109\/focs46700.2020.00112","type":"proceedings-article","created":{"date-parts":[[2021,3,17]],"date-time":"2021-03-17T11:21:26Z","timestamp":1615980086000},"page":"1168-1179","source":"Crossref","is-referenced-by-count":7,"title":["Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance"],"prefix":"10.1109","author":[{"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[]},{"given":"Barna","family":"Saha","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284322"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"ref31","first-page":"2012","article-title":"Accurate and nearly optimal sublinear approximations to ulam distance","author":"naumovitz","year":"2017","journal-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"journal-title":"A Linear Pattern Matching Algorithm","year":"1970","author":"morris","key":"ref30"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098003"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.71"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.15"},{"key":"ref11","first-page":"1170","article-title":"Approximating edit distance in truly subquadratic time: quantum and mapreduce","author":"boroujeni","year":"2018","journal-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"journal-title":"A simple sublinear algorithm for gap edit distance","year":"2020","author":"brakensiek","key":"ref12"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2746566"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294132"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00096"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897577"},{"key":"ref18","first-page":"34:1","article-title":"On estimating edit distance: Alignment, dimension reduction, and embeddings","volume":"107","author":"charikar","year":"2018","journal-title":"International Colloquium on Automata Languages and Programming ICALP"},{"key":"ref19","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","article-title":"Alignment of whole genomes","volume":"27","author":"delcher","year":"1999","journal-title":"Nucleic Acids Research"},{"key":"ref28","first-page":"707","article-title":"Binary Codes Capable of Correcting Deletions, Insertions and Reversals","volume":"10","author":"levenshtein","year":"1966","journal-title":"Soviet Physics Doklady"},{"key":"ref4","article-title":"Edit distance in near-linear time: it's a constant factor","author":"andoni","year":"2020","journal-title":"61st Annual IEEE Symposium on Foundations of Computer Science"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.8"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780590"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"ref1","first-page":"523","article-title":"Lower bounds for embedding edit distance into normed spaces","author":"andoni","year":"0","journal-title":"14th Annual ACM-SIAM symposium on Discrete algorithms"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.2307\/2034009"},{"key":"ref22","first-page":"657","author":"goldenberg","year":"2020","journal-title":"Does preprocessing help in fast sequence comparisons?"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00070"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00029"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384307"}],"event":{"name":"2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2020,11,16]]},"location":"Durham, NC, USA","end":{"date-parts":[[2020,11,19]]}},"container-title":["2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/9317865\/9317869\/09317955.pdf?arnumber=9317955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T22:21:18Z","timestamp":1657318878000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9317955\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":35,"URL":"https:\/\/doi.org\/10.1109\/focs46700.2020.00112","relation":{},"subject":[],"published":{"date-parts":[[2020,11]]}}}