{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T18:42:32Z","timestamp":1661971352353},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1137\/19m1272068","type":"journal-article","created":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T20:13:20Z","timestamp":1660853600000},"page":"1341-1367","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Longest Common Subsequence in Linear Time: Beating the $\\sqrt{{n}}$ Barrier"],"prefix":"10.1137","volume":"51","author":[{"given":"MohammadTaghi","family":"HajiAghayi","sequence":"first","affiliation":[]},{"given":"Masoud","family":"Seddighin","sequence":"additional","affiliation":[]},{"given":"Saeedreza","family":"Seddighin","sequence":"additional","affiliation":[]},{"given":"Xiaorui","family":"Sun","sequence":"additional","affiliation":[]}],"member":"351","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"atypb1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017","author":"Abboud A.","year":"2017"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"atypb3","volume-title":"Proceedings of the LIPIcs 9th Innovations in Theoretical Computer Science Conference (ITCS 2018","author":"Abboud A.","year":"2018"},{"key":"atypb4","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021","author":"Akmal S.","year":"2021"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536444"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840365"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003674"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"atypb12","volume-title":"Dynamic Programming","author":"Bellman R.","year":"1957"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.042"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.76"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.99"},{"key":"atypb17","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021","author":"Bringmann K.","year":"2021"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00096"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.040"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.100"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934514"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45123-4_15"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1971.11992886"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264437"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58338-6_63"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00071"},{"key":"atypb34","first-page":"436","volume":"48","author":"Tur\u00e1n P.","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321922"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T18:23:26Z","timestamp":1661970206000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1272068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["10.1137\/19M1272068"],"URL":"https:\/\/doi.org\/10.1137\/19m1272068","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8]]}}}