Paweł Gawrychowski

Fully dynamic longest increasing subsequence

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under(i) inserting an element, and(ii) deleting an element of an array.In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designe...[more]

28-Sep-2021