{"id":"https://openalex.org/W4390097887","doi":"https://doi.org/10.1109/focs57990.2023.00098","title":"Approximating Edit Distance in the Fully Dynamic Model","display_name":"Approximating Edit Distance in the Fully Dynamic Model","publication_year":2023,"publication_date":"2023-11-06","ids":{"openalex":"https://openalex.org/W4390097887","doi":"https://doi.org/10.1109/focs57990.2023.00098"},"language":"en","primary_location":{"id":"doi:10.1109/focs57990.2023.00098","is_oa":false,"landing_page_url":"https://doi.org/10.1109/focs57990.2023.00098","pdf_url":null,"source":null,"license":null,"license_id":null,"version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)","raw_type":"proceedings-article"},"type":"article","indexed_in":["crossref"],"open_access":{"is_oa":false,"oa_status":"closed","oa_url":null,"any_repository_has_fulltext":false},"authorships":[{"author_position":"first","author":{"id":"https://openalex.org/A5086467798","display_name":"Tomasz Kociumaka","orcid":"https://orcid.org/0000-0002-2477-1702"},"institutions":[{"id":"https://openalex.org/I4210109712","display_name":"Max Planck Institute for Informatics","ror":"https://ror.org/01w19ak89","country_code":"DE","type":"facility","lineage":["https://openalex.org/I149899117","https://openalex.org/I4210109712"]}],"countries":["DE"],"is_corresponding":true,"raw_author_name":"Tomasz Kociumaka","raw_affiliation_strings":["Saarland Informatics Campus,Max Planck Institute for Informatics,Saarbrücken,Germany"],"affiliations":[{"raw_affiliation_string":"Saarland Informatics Campus,Max Planck Institute for Informatics,Saarbrücken,Germany","institution_ids":["https://openalex.org/I4210109712"]}]},{"author_position":"middle","author":{"id":"https://openalex.org/A5046919162","display_name":"Anish Mukherjee","orcid":"https://orcid.org/0000-0002-5857-9778"},"institutions":[{"id":"https://openalex.org/I39555362","display_name":"University of Warwick","ror":"https://ror.org/01a77tt86","country_code":"GB","type":"education","lineage":["https://openalex.org/I39555362"]}],"countries":["GB"],"is_corresponding":false,"raw_author_name":"Anish Mukherjee","raw_affiliation_strings":["University of Warwick,Dept. of Computer Science,Coventry,UK","Dept. of Computer Science, University of Warwick, Coventry, UK"],"affiliations":[{"raw_affiliation_string":"University of Warwick,Dept. of Computer Science,Coventry,UK","institution_ids":["https://openalex.org/I39555362"]},{"raw_affiliation_string":"Dept. of Computer Science, University of Warwick, Coventry, UK","institution_ids":["https://openalex.org/I39555362"]}]},{"author_position":"last","author":{"id":"https://openalex.org/A5110611660","display_name":"Barna Saha","orcid":null},"institutions":[{"id":"https://openalex.org/I36258959","display_name":"University of California, San Diego","ror":"https://ror.org/0168r3w48","country_code":"US","type":"education","lineage":["https://openalex.org/I36258959"]}],"countries":["US"],"is_corresponding":false,"raw_author_name":"Barna Saha","raw_affiliation_strings":["University of California,Dept. of Computer Science & Engineering,San Diego,US"],"affiliations":[{"raw_affiliation_string":"University of California,Dept. of Computer Science & Engineering,San Diego,US","institution_ids":["https://openalex.org/I36258959"]}]}],"institutions":[],"countries_distinct_count":3,"institutions_distinct_count":3,"corresponding_author_ids":["https://openalex.org/A5086467798"],"corresponding_institution_ids":["https://openalex.org/I4210109712"],"apc_list":null,"apc_paid":null,"fwci":0.1748,"has_fulltext":false,"cited_by_count":1,"citation_normalized_percentile":{"value":0.59013865,"is_in_top_1_percent":false,"is_in_top_10_percent":false},"cited_by_percentile_year":{"min":91,"max":95},"biblio":{"volume":null,"issue":null,"first_page":"1628","last_page":"1638"},"is_retracted":false,"is_paratext":false,"is_xpac":false,"primary_topic":{"id":"https://openalex.org/T11269","display_name":"Algorithms and Data Compression","score":0.9998999834060669,"subfield":{"id":"https://openalex.org/subfields/1702","display_name":"Artificial Intelligence"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},"topics":[{"id":"https://openalex.org/T11269","display_name":"Algorithms and Data Compression","score":0.9998999834060669,"subfield":{"id":"https://openalex.org/subfields/1702","display_name":"Artificial Intelligence"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T12326","display_name":"Network Packet Processing and Optimization","score":0.9833999872207642,"subfield":{"id":"https://openalex.org/subfields/1708","display_name":"Hardware and Architecture"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T10181","display_name":"Natural Language Processing Techniques","score":0.9815999865531921,"subfield":{"id":"https://openalex.org/subfields/1702","display_name":"Artificial Intelligence"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}}],"keywords":[{"id":"https://openalex.org/keywords/edit-distance","display_name":"Edit distance","score":0.9739990234375},{"id":"https://openalex.org/keywords/sublinear-function","display_name":"Sublinear function","score":0.7394698262214661},{"id":"https://openalex.org/keywords/string","display_name":"String (physics)","score":0.5315454006195068},{"id":"https://openalex.org/keywords/approximation-algorithm","display_name":"Approximation algorithm","score":0.5123535394668579},{"id":"https://openalex.org/keywords/computer-science","display_name":"Computer science","score":0.4545147120952606},{"id":"https://openalex.org/keywords/algorithm","display_name":"Algorithm","score":0.44647279381752014},{"id":"https://openalex.org/keywords/similarity","display_name":"Similarity (geometry)","score":0.4322560131549835},{"id":"https://openalex.org/keywords/combinatorics","display_name":"Combinatorics","score":0.42982059717178345},{"id":"https://openalex.org/keywords/sequence","display_name":"Sequence (biology)","score":0.427813857793808},{"id":"https://openalex.org/keywords/bounding-overwatch","display_name":"Bounding overwatch","score":0.4212832450866699},{"id":"https://openalex.org/keywords/dynamic-programming","display_name":"Dynamic programming","score":0.4159984886646271},{"id":"https://openalex.org/keywords/measure","display_name":"Measure (data warehouse)","score":0.4110947251319885},{"id":"https://openalex.org/keywords/discrete-mathematics","display_name":"Discrete mathematics","score":0.3852630853652954},{"id":"https://openalex.org/keywords/mathematics","display_name":"Mathematics","score":0.3351185619831085},{"id":"https://openalex.org/keywords/artificial-intelligence","display_name":"Artificial intelligence","score":0.11313194036483765}],"concepts":[{"id":"https://openalex.org/C44359876","wikidata":"https://www.wikidata.org/wiki/Q5338467","display_name":"Edit distance","level":2,"score":0.9739990234375},{"id":"https://openalex.org/C117160843","wikidata":"https://www.wikidata.org/wiki/Q338652","display_name":"Sublinear function","level":2,"score":0.7394698262214661},{"id":"https://openalex.org/C157486923","wikidata":"https://www.wikidata.org/wiki/Q1376436","display_name":"String (physics)","level":2,"score":0.5315454006195068},{"id":"https://openalex.org/C148764684","wikidata":"https://www.wikidata.org/wiki/Q621751","display_name":"Approximation algorithm","level":2,"score":0.5123535394668579},{"id":"https://openalex.org/C41008148","wikidata":"https://www.wikidata.org/wiki/Q21198","display_name":"Computer science","level":0,"score":0.4545147120952606},{"id":"https://openalex.org/C11413529","wikidata":"https://www.wikidata.org/wiki/Q8366","display_name":"Algorithm","level":1,"score":0.44647279381752014},{"id":"https://openalex.org/C103278499","wikidata":"https://www.wikidata.org/wiki/Q254465","display_name":"Similarity (geometry)","level":3,"score":0.4322560131549835},{"id":"https://openalex.org/C114614502","wikidata":"https://www.wikidata.org/wiki/Q76592","display_name":"Combinatorics","level":1,"score":0.42982059717178345},{"id":"https://openalex.org/C2778112365","wikidata":"https://www.wikidata.org/wiki/Q3511065","display_name":"Sequence (biology)","level":2,"score":0.427813857793808},{"id":"https://openalex.org/C63584917","wikidata":"https://www.wikidata.org/wiki/Q333286","display_name":"Bounding overwatch","level":2,"score":0.4212832450866699},{"id":"https://openalex.org/C37404715","wikidata":"https://www.wikidata.org/wiki/Q380679","display_name":"Dynamic programming","level":2,"score":0.4159984886646271},{"id":"https://openalex.org/C2780009758","wikidata":"https://www.wikidata.org/wiki/Q6804172","display_name":"Measure (data warehouse)","level":2,"score":0.4110947251319885},{"id":"https://openalex.org/C118615104","wikidata":"https://www.wikidata.org/wiki/Q121416","display_name":"Discrete mathematics","level":1,"score":0.3852630853652954},{"id":"https://openalex.org/C33923547","wikidata":"https://www.wikidata.org/wiki/Q395","display_name":"Mathematics","level":0,"score":0.3351185619831085},{"id":"https://openalex.org/C154945302","wikidata":"https://www.wikidata.org/wiki/Q11660","display_name":"Artificial intelligence","level":1,"score":0.11313194036483765},{"id":"https://openalex.org/C115961682","wikidata":"https://www.wikidata.org/wiki/Q860623","display_name":"Image (mathematics)","level":2,"score":0.0},{"id":"https://openalex.org/C77088390","wikidata":"https://www.wikidata.org/wiki/Q8513","display_name":"Database","level":1,"score":0.0},{"id":"https://openalex.org/C37914503","wikidata":"https://www.wikidata.org/wiki/Q156495","display_name":"Mathematical physics","level":1,"score":0.0},{"id":"https://openalex.org/C54355233","wikidata":"https://www.wikidata.org/wiki/Q7162","display_name":"Genetics","level":1,"score":0.0},{"id":"https://openalex.org/C86803240","wikidata":"https://www.wikidata.org/wiki/Q420","display_name":"Biology","level":0,"score":0.0}],"mesh":[],"locations_count":2,"locations":[{"id":"doi:10.1109/focs57990.2023.00098","is_oa":false,"landing_page_url":"https://doi.org/10.1109/focs57990.2023.00098","pdf_url":null,"source":null,"license":null,"license_id":null,"version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)","raw_type":"proceedings-article"},{"id":"pmh:oai:wrap.warwick.ac.uk:184025","is_oa":false,"landing_page_url":null,"pdf_url":null,"source":{"id":"https://openalex.org/S4306400665","display_name":"Warwick Research Archive Portal (University of Warwick)","issn_l":null,"issn":null,"is_oa":false,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I39555362","host_organization_name":"University of Warwick","host_organization_lineage":["https://openalex.org/I39555362"],"host_organization_lineage_names":[],"type":"repository"},"license":null,"license_id":null,"version":"acceptedVersion","is_accepted":true,"is_published":false,"raw_source_name":"","raw_type":"Conference Item"}],"best_oa_location":null,"sustainable_development_goals":[],"awards":[{"id":"https://openalex.org/G2774561655","display_name":null,"funder_award_id":"EP/V01305X/1","funder_id":"https://openalex.org/F4320334627","funder_display_name":"Engineering and Physical Sciences Research Council"}],"funders":[{"id":"https://openalex.org/F4320334627","display_name":"Engineering and Physical Sciences Research Council","ror":"https://ror.org/0439y7842"}],"has_content":{"grobid_xml":false,"pdf":false},"content_urls":null,"referenced_works_count":84,"referenced_works":["https://openalex.org/W1764956874","https://openalex.org/W1806839752","https://openalex.org/W1969844791","https://openalex.org/W1970026646","https://openalex.org/W1974708980","https://openalex.org/W1977618577","https://openalex.org/W1982440947","https://openalex.org/W1983248819","https://openalex.org/W1985572324","https://openalex.org/W1991099830","https://openalex.org/W1991306532","https://openalex.org/W2012714839","https://openalex.org/W2016973429","https://openalex.org/W2032869782","https://openalex.org/W2074231493","https://openalex.org/W2074707165","https://openalex.org/W2078993594","https://openalex.org/W2099450374","https://openalex.org/W2106184136","https://openalex.org/W2133601898","https://openalex.org/W2168023916","https://openalex.org/W2178011018","https://openalex.org/W2178621981","https://openalex.org/W2207058206","https://openalex.org/W2249898666","https://openalex.org/W2342666984","https://openalex.org/W2401697020","https://openalex.org/W2571471359","https://openalex.org/W2664802502","https://openalex.org/W2810672408","https://openalex.org/W2888157438","https://openalex.org/W2951922466","https://openalex.org/W2952708184","https://openalex.org/W2962710088","https://openalex.org/W2963012630","https://openalex.org/W2963645943","https://openalex.org/W2964007887","https://openalex.org/W2964264613","https://openalex.org/W2971415725","https://openalex.org/W2971787908","https://openalex.org/W2971800005","https://openalex.org/W2972083972","https://openalex.org/W3002774327","https://openalex.org/W3034398078","https://openalex.org/W3034399032","https://openalex.org/W3034952850","https://openalex.org/W3035231910","https://openalex.org/W3035518111","https://openalex.org/W3037236243","https://openalex.org/W3045093866","https://openalex.org/W3097495782","https://openalex.org/W3125058277","https://openalex.org/W3126626577","https://openalex.org/W3127039040","https://openalex.org/W3127593639","https://openalex.org/W3127776752","https://openalex.org/W3128057791","https://openalex.org/W3128132474","https://openalex.org/W3129012052","https://openalex.org/W3135932689","https://openalex.org/W3138321435","https://openalex.org/W3162057152","https://openalex.org/W3167872191","https://openalex.org/W3169904088","https://openalex.org/W3217016244","https://openalex.org/W4210631930","https://openalex.org/W4229488000","https://openalex.org/W4232943531","https://openalex.org/W4281643687","https://openalex.org/W4281704174","https://openalex.org/W4282042973","https://openalex.org/W4291144019","https://openalex.org/W4316652249","https://openalex.org/W4376651378","https://openalex.org/W6658197196","https://openalex.org/W6669601524","https://openalex.org/W6691573301","https://openalex.org/W6691614050","https://openalex.org/W6768718198","https://openalex.org/W6779065642","https://openalex.org/W6780024218","https://openalex.org/W6795550245","https://openalex.org/W6810059355","https://openalex.org/W6860039148"],"related_works":["https://openalex.org/W90906771","https://openalex.org/W2018828772","https://openalex.org/W2529185025","https://openalex.org/W2052708136","https://openalex.org/W2809723425","https://openalex.org/W2005302727","https://openalex.org/W4289097813","https://openalex.org/W3082028334","https://openalex.org/W4376639521","https://openalex.org/W2044210752"],"abstract_inverted_index":{"The":[0,66,136,156,270],"edit":[1,43,75,105,145,158,188,201,327],"distance":[2,44,76,106,146,159,189,202,328],"is":[3,50,138,176,197,239,275,301],"a":[4,37,229,276],"fundamental":[5],"measure":[6],"of":[7,15,32,96,130,132,147,272,285,310,322,354],"sequence":[8],"similarity,":[9],"defined":[10],"as":[11,113],"the":[12,27,52,60,79,94,103,109,114,133,141,153,184,192,205,261,292,303,307,311],"minimum":[13],"number":[14],"character":[16],"insertions,":[17],"deletions,":[18],"and":[19,89,211,225,228,263,294,348],"substitutions":[20],"needed":[21],"to":[22,56,85,87,91,139,241,298,337],"transform":[23],"one":[24],"string":[25,361],"into":[26],"other.":[28],"Given":[29],"two":[30,134],"strings":[31,110,150,232],"length":[33],"at":[34,93,127],"most":[35],"n,":[36],"simple":[38],"dynamic":[39,104,149,200,231,277,360],"programming":[40],"computes":[41],"their":[42],"exactly":[45],"in":[46,74,163,187,191,245,313,359],"$\\mathcal{O}\\left(n^{2}\\right)$":[47],"time,":[48],"which":[49,175,300,343],"also":[51,302],"best":[53,206,304],"possible":[54,240,305],"(up":[55],"subpolynomial":[57],"factors)":[58],"assuming":[59,179],"Strong":[61],"Exponential":[62],"Time":[63],"Hypothesis":[64],"(SETH).":[65],"last":[67],"few":[68],"decades":[69],"have":[70],"seen":[71],"tremendous":[72],"progress":[73,186],"approximation,":[77],"where":[78,108],"runtime":[80],"has":[81],"been":[82],"brought":[83],"down":[84,297],"subquadratic,":[86],"near-linear,":[88],"even":[90,182],"sublinear":[92],"cost":[95],"approximation.":[97,203],"In":[98,287],"this":[99,257,273],"paper,":[100],"we":[101,290],"study":[102],"problem":[107],"change":[111,124],"dynamically":[112,338],"characters":[115],"are":[116],"substituted,":[117],"inserted,":[118],"or":[119,143],"deleted":[120],"over":[121],"time.":[122,155],"Each":[123],"may":[125],"happen":[126],"any":[128,250],"location":[129],"either":[131],"strings.":[135],"goal":[137],"maintain":[140,339],"(exact":[142],"approximate)":[144],"such":[148],"while":[151],"minimizing":[152],"update":[154,170,247,283],"exact":[157,222],"can":[160,349],"be":[161,350],"maintained":[162],"$\\mathcal{O}\\left(n":[164],"\\log":[165],"^{2}":[166],"n\\right)$":[167],"time":[168,248,284],"per":[169],"(Charalampopoulos,":[171],"Kociumaka,":[172,214],"Mozes;":[173],"2020),":[174],"again":[177],"tight":[178],"SETH.":[180],"Unfortunately,":[181],"with":[183,280,306,345],"unprecedented":[185],"approximation":[190,218,329],"static":[193,314],"setting,":[194],"strikingly":[195],"little":[196],"known":[198],"regarding":[199],"Utilizing":[204],"near-linear-time":[207],"(Andoni,":[208,330],"Nosatzki;":[209],"2020)":[210],"sublinear-time":[212],"(Goldenberg,":[213],"Krauthgamer,":[215,331],"Saha;":[216],"2022)":[217],"algorithm,":[219],"an":[220,243,319,351],"old":[221],"algorithm":[223,279],"(Landau":[224],"Vishkin;":[226],"1988),":[227],"generic":[230],"implementation":[233],"(Mehlhorn,":[234],"Sundar,":[235],"Uhrig;":[236],"1996),":[237],"it":[238],"achieve":[242],"$\\mathcal{O}\\left(n^{c}\\right)$-approximation":[244],"$n^{0.5-c+o(1)}$":[246],"for":[249,326,356],"constant":[251],"$c":[252],"\\in\\left[0,":[253],"\\frac{1}{6}\\right]$.":[254],"Improving":[255],"upon":[256],"trade-off,":[258],"characterized":[259],"by":[260],"approximation-ratio":[262,293],"update-time":[264,295],"product":[265,296],"$n^{0.5+o(1)}$,":[266],"remains":[267],"wide":[268],"open.":[269],"contribution":[271],"work":[274],"$n^{o(1)}$-approximation":[278],"amortized":[281],"expected":[282],"$n^{o(1)}$.":[286],"other":[288],"words,":[289],"bring":[291],"$n^{o(1)}$,":[299],"current":[308],"state":[309],"art":[312],"algorithms.":[315,362],"Our":[316],"solution":[317],"utilizes":[318],"elegant":[320],"framework":[321],"precision":[323,340],"sampling":[324,341],"trees":[325],"Onak;":[332],"2010).":[333],"We":[334],"show":[335],"how":[336],"trees,":[342],"comes":[344],"significant":[346],"nontriviality":[347],"independent":[352],"tool":[353],"interest":[355],"further":[357],"development":[358]},"counts_by_year":[{"year":2025,"cited_by_count":1}],"updated_date":"2025-11-06T03:46:38.306776","created_date":"2025-10-10T00:00:00"}