{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:23:11Z","timestamp":1787494991999,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 1535795, CCF-1563710"],"award-info":[{"award-number":["CCF- 1535795, CCF-1563710"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384240","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T17:48:11Z","timestamp":1624902491000},"page":"671-684","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Dynamic algorithms for LIS and distance to monotonicity"],"prefix":"10.1145","author":[{"given":"Michael","family":"Mitzenmacher","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3951-7096","authenticated-orcid":false,"given":"Saeed","family":"Seddighin","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"RANDOM","author":"Ailon N.","year":"2004","unstructured":"N. Ailon , B. Chazelle , S. Comandur , and D. Liu . Estimating the distance to a monotone function . In RANDOM 2004 . N. Ailon, B. Chazelle, S. Comandur, and D. Liu. Estimating the distance to a monotone function. In RANDOM 2004."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.8"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.116"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_1_6_1","first-page":"1189","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Boroujeni M.","unstructured":"M. Boroujeni , S. Ehsani , M. Ghodsi , M. HajiAghayi , and S. Seddighin . Approximating edit distance in truly subquadratic time: Quantum and mapreduce . In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1170\u2013 1189 . SIAM, 2018. M. Boroujeni, S. Ehsani, M. Ghodsi, M. HajiAghayi, and S. Seddighin. Approximating edit distance in truly subquadratic time: Quantum and mapreduce. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1170\u20131189. SIAM, 2018."},{"key":"e_1_3_2_1_7_1","first-page":"1620","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Boroujeni M.","unstructured":"M. Boroujeni , M. Seddighin , and S. Seddighin . Improved algorithms for edit distance and lcs: Beyond worst case . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1601\u2013 1620 . SIAM, 2020. M. Boroujeni, M. Seddighin, and S. Seddighin. Improved algorithms for edit distance and lcs: Beyond worst case. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1601\u20131620. SIAM, 2020."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323205"},{"key":"e_1_3_2_1_9_1","first-page":"990","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Chakraborty D.","unstructured":"D. Chakraborty , D. Das , E. Goldenberg , M. Koucky , and M. Saks . Approximating edit distance within constant factor in truly sub-quadratic time . In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 979\u2013 990 . IEEE, 2018. D. Chakraborty, D. Das, E. Goldenberg, M. Koucky, and M. Saks. Approximating edit distance within constant factor in truly sub-quadratic time. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 979\u2013990. IEEE, 2018."},{"key":"e_1_3_2_1_10_1","volume-title":"The dynamic longest increasing subsequence problem. arXiv preprint arXiv:1309.7724","author":"Chen A.","year":"2013","unstructured":"A. Chen , T. Chu , and N. Pinsker . The dynamic longest increasing subsequence problem. arXiv preprint arXiv:1309.7724 , 2013 . A. Chen, T. Chu, and N. Pinsker. The dynamic longest increasing subsequence problem. arXiv preprint arXiv:1309.7724, 2013."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_20"},{"key":"e_1_3_2_1_12_1","volume-title":"Algorithms","author":"Dasgupta S.","year":"2008","unstructured":"S. Dasgupta , C. H. Papadimitriou , and U. V. Vazirani . Algorithms . McGraw-Hill Higher Education , 2008 . S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. McGraw-Hill Higher Education, 2008."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"e_1_3_2_1_14_1","volume-title":"Spot-checkers. In STOC","author":"Erg\u00fcn F.","year":"1998","unstructured":"F. Erg\u00fcn , S. Kannan , R. Kumar , R. Rubinfeld , and M. Viswanathan . Spot-checkers. In STOC 1998 . F. Erg\u00fcn, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers. In STOC 1998."},{"key":"e_1_3_2_1_15_1","first-page":"97","article-title":"The art of uninformed decisions","volume":"75","author":"Fischer E.","year":"2001","unstructured":"E. Fischer . The art of uninformed decisions . Bulletin of the EATCS , 75 : 97 , 2001 . E. Fischer. The art of uninformed decisions. Bulletin of the EATCS, 75:97, 2001.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.54"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.99"},{"key":"e_1_3_2_1_19_1","volume-title":"SODA","author":"Gopalan P.","year":"2007","unstructured":"P. Gopalan , T. S. Jayram , R. Krauthgamer , and R. Kumar . Estimating the sortedness of a data stream . In SODA 2007 . P. Gopalan, T. S. Jayram, R. Krauthgamer, and R. Kumar. Estimating the sortedness of a data stream. In SODA 2007."},{"key":"e_1_3_2_1_20_1","first-page":"1672","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Hajiaghayi M.","unstructured":"M. Hajiaghayi , S. Seddighin , and X. Sun . Massively parallel approximation algorithms for edit distance and longest common subsequence . In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1654\u2013 1672 . SIAM, 2019. M. Hajiaghayi, S. Seddighin, and X. Sun. Massively parallel approximation algorithms for edit distance and longest common subsequence. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1654\u20131672. SIAM, 2019."},{"key":"e_1_3_2_1_21_1","volume-title":"FOCS","author":"Han Y.","year":"2002","unstructured":"Y. Han and M. Thorup . Integer sorting in o(n\u221alog log n) expected time and linear space . In FOCS 2002 . Y. Han and M. Thorup. Integer sorting in o(n\u221alog log n) expected time and linear space. In FOCS 2002."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_24_1","first-page":"66","volume-title":"Annual Symposium on Combinatorial Pattern Matching","author":"Jacobson G.","unstructured":"G. Jacobson and K.-P. Vo. Heaviest increasing\/common subsequence problems. In Annual Symposium on Combinatorial Pattern Matching , pages 52\u2013 66 . Springer, 1992. G. Jacobson and K.-P. Vo. Heaviest increasing\/common subsequence problems. In Annual Symposium on Combinatorial Pattern Matching, pages 52\u201366. Springer, 1992."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746615"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.131"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.26"},{"key":"e_1_3_2_1_30_1","volume-title":"International journal of computer mathematics, 65(3-4):161\u2013164","author":"Ramanan P.","year":"1997","unstructured":"P. Ramanan . Tight \u03c9 (n log n) lower bound for finding a longest increasing subsequence. International journal of computer mathematics, 65(3-4):161\u2013164 , 1997 . P. Ramanan. Tight \u03c9 (n log n) lower bound for finding a longest increasing subsequence. International journal of computer mathematics, 65(3-4):161\u2013164, 1997."},{"key":"e_1_3_2_1_31_1","volume-title":"FOCS","author":"Runbinstein A.","year":"2019","unstructured":"A. Runbinstein , S. Seddighin , Z. Song , and X. Sun . Approximation algorithms for LCS and LIS with truly improved running times . In FOCS , 2019 . A. Runbinstein, S. Seddighin, Z. Song, and X. Sun. Approximation algorithms for LCS and LIS with truly improved running times. In FOCS, 2019."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.51"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181889"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780566"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384240","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":34,"alternative-id":["10.1145\/3357713.3384240","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384240","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}