{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:20Z","timestamp":1750694780482,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451137","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"654-667","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Fully dynamic approximation of LIS in polylogarithmic time"],"prefix":"10.1145","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Janczewski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"volume-title":"56th FOCS. Pages 59\u201378.","author":"Abboud Amir","key":"e_1_3_2_1_1_1","unstructured":"Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In 56th FOCS. Pages 59\u201378."},{"key":"e_1_3_2_1_2_1","first-page":"1","article-title":"Tighter Connections Between Formula-SAT and Shaving Logs. In 45th ICALP","volume":"8","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud and Karl Bringmann. 2018. Tighter Connections Between Formula-SAT and Shaving Logs. In 45th ICALP. Pages 8:1\u20138:18.","journal-title":"Pages"},{"volume-title":"Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms","author":"Abboud Amir","key":"e_1_3_2_1_3_1","unstructured":"Amir Abboud and S\u00f8 ren Dahlgaard. 2016. Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. In FOCS. IEEE Computer Society. Pages 477\u2013486."},{"key":"e_1_3_2_1_4_1","first-page":"2","article-title":"An algorithm for organization of information","volume":"146","author":"Adelson-Velski George M.","year":"1962","unstructured":"George M. Adelson-Velski and Evgenii M. Landis. 1962. An algorithm for organization of information. Doklady Akademii Nauk, 146, 2, 1962. Pages 263\u2013266.","journal-title":"Doklady Akademii Nauk"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-99-00796-X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Negev Shekel Nosatzki. 2020. Edit Distance in Near-Linear Time: it's a Constant Factor. In FOCS. IEEE. Pages 990\u20131001.","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi Krzysztof Onak Baruch Schieber and Shay Solomon. 2018. Fully dynamic maximal independent set with sublinear update time. In STOC. ACM. Pages 815\u2013826.","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi Krzysztof Onak Baruch Schieber and Shay Solomon. 2019. Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. In SODA. SIAM. Pages 1919\u20131936.","DOI":"10.1137\/1.9781611975482.116"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050126"},{"volume-title":"Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time","author":"Behnezhad Soheil","key":"e_1_3_2_1_10_1","unstructured":"Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. 2019. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. In FOCS. IEEE Computer Society. Pages 382\u2013405."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3344999"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein Maximilian Probst and Christian Wulff-Nilsen. 2019. Decremental strongly-connected components and single-source reachability in near-linear time. In STOC. ACM. Pages 365\u2013376.","DOI":"10.1145\/3313276.3316335"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein and Cliff Stein. 2016. Faster Fully Dynamic Matchings with Small Approximation Ratios. In SODA. SIAM. Pages 692\u2013711.","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00630-4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.042"},{"key":"e_1_3_2_1_16_1","first-page":"6","article-title":"On Partitions of Permutations into Increasing and Decreasing Subsequences","volume":"22","author":"Brandst\u00e4dt Andreas","year":"1986","unstructured":"Andreas Brandst\u00e4dt and Dieter Kratsch. 1986. On Partitions of Permutations into Increasing and Decreasing Subsequences. J. Inf. Process. Cybern., 22, 5\/6, 1986. Pages 263\u2013273.","journal-title":"J. Inf. Process. Cybern."},{"volume-title":"56th FOCS. Pages 79\u201397.","author":"Bringmann Karl","key":"e_1_3_2_1_17_1","unstructured":"Karl Bringmann and Marvin K\u00fcnnemann. 2015. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In 56th FOCS. Pages 79\u201397."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Diptarka Chakraborty Lior Kamma and Kasper Green Larsen. 2018. Tight cell probe bounds for succinct Boolean matrix-vector multiplication. In STOC. ACM. Pages 1297\u20131306.","DOI":"10.1145\/3188745.3188830"},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"Dynamic String Alignment","volume":"9","author":"Charalampopoulos Panagiotis","year":"2020","unstructured":"Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes. 2020. Dynamic String Alignment. In CPM. LIPIcs. 161, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Pages 9:1\u20139:13.","journal-title":"CPM. LIPIcs. 161, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Pages"},{"key":"e_1_3_2_1_20_1","volume-title":"Computing the Longest Increasing Subsequence of a Sequence Subject to Dynamic Insertion. CoRR, abs\/1309.7724","author":"Chen Alex","year":"2013","unstructured":"Alex Chen, Timothy Chu, and Nathan Pinsker. 2013. Computing the Longest Increasing Subsequence of a Sequence Subject to Dynamic Insertion. CoRR, abs\/1309.7724, 2013."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.04.003"},{"key":"e_1_3_2_1_22_1","volume-title":"Daniel Dominic Sleator, and Robert Endre Tarjan","author":"Driscoll James R.","year":"1986","unstructured":"James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan. 1986. Making Data Structures Persistent. In STOC. ACM. Pages 109\u2013121."},{"key":"e_1_3_2_1_23_1","first-page":"1935","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u00f6s Paul","year":"1935","unstructured":"Paul Erd\u00f6s and George Szekeres. 1935. A combinatorial problem in geometry. Compositio Mathematica, 2, 1935. Pages 463\u2013470.","journal-title":"Compositio Mathematica"},{"key":"e_1_3_2_1_24_1","unstructured":"Funda Erg\u00fcn and Hossein Jowhari. 2008. On distance to monotonicity and longest increasing subsequence of a data stream. In SODA. SIAM. Pages 730\u2013736."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770801"},{"key":"e_1_3_2_1_28_1","volume-title":"Fully Dynamic Approximation of LIS in Polylogarithmic Time. CoRR, abs\/2011.09761","author":"Gawrychowski Pawel","year":"2020","unstructured":"Pawel Gawrychowski and Wojciech Janczewski. 2020. Fully Dynamic Approximation of LIS in Polylogarithmic Time. CoRR, abs\/2011.09761, 2020."},{"key":"e_1_3_2_1_29_1","volume-title":"Conditional Lower Bounds for Variants of Dynamic LIS. CoRR, abs\/2102.11797","author":"Gawrychowski Pawel","year":"2021","unstructured":"Pawel Gawrychowski and Wojciech Janczewski. 2021. Conditional Lower Bounds for Variants of Dynamic LIS. CoRR, abs\/2102.11797, 2021."},{"key":"e_1_3_2_1_30_1","unstructured":"Parikshit Gopalan T. S. Jayram Robert Krauthgamer and Ravi Kumar. 2007. Estimating the sortedness of a data stream. In SODA. SIAM. Pages 318\u2013327."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.040"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Fabrizio Grandoni Giuseppe F. Italiano Aleksander Lukasiewicz Nikos Parotsidis and Przemyslaw Uznanski. 2021. All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier. In SODA. SIAM. Pages 273\u2013289.","DOI":"10.1137\/1.9781611976465.18"},{"key":"e_1_3_2_1_33_1","first-page":"4","article-title":"Threesomes, Degenerates, and Love Triangles","volume":"65","author":"Seth Pettie Allan Gr\u00f8","year":"2018","unstructured":"Allan Gr\u00f8 nlund and Seth Pettie. 2018. Threesomes, Degenerates, and Love Triangles. J. ACM, 65, 4, 2018. Pages 22:1\u201322:25.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_34_1","volume-title":"Virginia Vassilevska Williams, and Nicole Wein","author":"Gutenberg Maximilian Probst","year":"2020","unstructured":"Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. 2020. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In STOC. ACM. Pages 153\u2013166."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Maximilian Probst Gutenberg and Christian Wulff-Nilsen. 2020. Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary. In SODA. SIAM. Pages 2542\u20132561.","DOI":"10.1137\/1.9781611975994.155"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Maximilian Probst Gutenberg and Christian Wulff-Nilsen. 2020. Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler. In SODA. SIAM. Pages 2522\u20132541.","DOI":"10.1137\/1.9781611975994.154"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Maximilian Probst Gutenberg and Christian Wulff-Nilsen. 2020. Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds. In SODA. SIAM. Pages 2562\u20132574.","DOI":"10.1137\/1.9781611975994.156"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"MohammadTaghi Hajiaghayi Masoud Seddighin Saeed Seddighin and Xiaorui Sun. 2019. Approximating LCS in Linear Time: Beating the \\sqrt n Barrier. In SODA. SIAM. Pages 1181\u20131200.","DOI":"10.1137\/1.9781611975482.72"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Monika Henzinger Sebastian Krinninger Danupon Nanongkai and Thatchaphol Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In STOC. ACM. Pages 21\u201330.","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3285953"},{"key":"e_1_3_2_1_42_1","first-page":"1","article-title":"Space-Efficient Algorithms for Longest Increasing Subsequence","volume":"44","author":"Kiyomi Masashi","year":"2018","unstructured":"Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, and Jun Tarui. 2018. Space-Efficient Algorithms for Longest Increasing Subsequence. In STACS. LIPIcs. 96, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Pages 44:1\u201344:15.","journal-title":"STACS. LIPIcs. 96, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Pages"},{"key":"e_1_3_2_1_43_1","volume-title":"Improved Dynamic Algorithms for Longest Increasing Subsequence. CoRR, abs\/2011.10874","author":"Kociumaka Tomasz","year":"2020","unstructured":"Tomasz Kociumaka and Saeed Seddighin. 2020. Improved Dynamic Algorithms for Longest Increasing Subsequence. CoRR, abs\/2011.10874, 2020."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Kasper Green Larsen and R. Ryan Williams. 2017. Faster Online Matrix-Vector Multiplication. In SODA. SIAM. Pages 2182\u20132189.","DOI":"10.1137\/1.9781611974782.142"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Jakub \\L \u0105cki Jakub O\u0107wieja Marcin Pilipczuk Piotr Sankowski and Anna Zych. 2015. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. In STOC. ACM. Pages 11\u201320.","DOI":"10.1145\/2746539.2746615"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher and Saeed Seddighin. 2020. Dynamic algorithms for LIS and distance to monotonicity. In STOC. ACM. Pages 671\u2013684.","DOI":"10.1145\/3357713.3384240"},{"key":"e_1_3_2_1_48_1","volume-title":"Erd\u00f6s-Szekeres Partitioning Problem. CoRR, abs\/2011.10870","author":"Mitzenmacher Michael","year":"2020","unstructured":"Michael Mitzenmacher and Saeed Seddighin. 2020. Erd\u00f6s-Szekeres Partitioning Problem. CoRR, abs\/2011.10870, 2020."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Danupon Nanongkai and Thatchaphol Saranurak. 2017. Dynamic spanning forest with worst-case update time: adaptive Las Vegas and O(n^1\/2-\\epsilon )-time. In STOC. ACM. Pages 1122\u20131129.","DOI":"10.1145\/3055399.3055447"},{"volume-title":"Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time","author":"Nanongkai Danupon","key":"e_1_3_2_1_50_1","unstructured":"Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. 2017. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In FOCS. IEEE Computer Society. Pages 950\u2013961."},{"key":"e_1_3_2_1_51_1","volume-title":"Saks","author":"Naumovitz Timothy","year":"2015","unstructured":"Timothy Naumovitz and Michael E. Saks. 2015. A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. In SODA. SIAM. Pages 1252\u20131262."},{"key":"e_1_3_2_1_52_1","volume-title":"New Algorithms and Lower Bounds for LIS Estimation. CoRR, abs\/2010.05805","author":"Newman Ilan","year":"2020","unstructured":"Ilan Newman and Nithin Varma. 2020. New Algorithms and Lower Bounds for LIS Estimation. CoRR, abs\/2010.05805, 2020."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207169708804607"},{"volume-title":"Approximation Algorithms for LCS and LIS with Truly Improved Running Times","author":"Rubinstein Aviad","key":"e_1_3_2_1_54_1","unstructured":"Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. 2019. Approximation Algorithms for LCS and LIS with Truly Improved Running Times. In FOCS. IEEE Computer Society. Pages 1121\u20131145."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Aviad Rubinstein and Zhao Song. 2020. Reducing approximate Longest Common Subsequence to approximate Edit Distance. In SODA. SIAM. Pages 1591\u20131600.","DOI":"10.1137\/1.9781611975994.98"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Michael E. Saks and C. Seshadhri. 2013. Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. In SODA. SIAM. Pages 1698\u20131709.","DOI":"10.1137\/1.9781611973105.122"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/130942152"},{"key":"e_1_3_2_1_58_1","volume-title":"Semi-local string comparison: algorithmic techniques and applications. CoRR, abs\/0707.3619","author":"Tiskin Alexandre","year":"2007","unstructured":"Alexandre Tiskin. 2007. Semi-local string comparison: algorithmic techniques and applications. CoRR, abs\/0707.3619, 2007."},{"key":"e_1_3_2_1_59_1","first-page":"3","article-title":"Preserving Order in a Forest in Less Than Logarithmic Time and Linear","volume":"6","author":"van Emde Boas Peter","year":"1977","unstructured":"Peter van Emde Boas. 1977. Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space. Inf. Process. Lett., 6, 3, 1977. Pages 80\u201382.","journal-title":"Space. Inf. Process. Lett."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Christian Wulff-Nilsen. 2017. Fully-dynamic minimum spanning forest with improved worst-case update time. In STOC. ACM. Pages 1130\u20131143.","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451137","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:54Z","timestamp":1750195494000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":60,"alternative-id":["10.1145\/3406325.3451137","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451137","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}