Séminaire

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] designed an algorithm that maintains an O((1/ϵ)^O(1/ϵ))-approximation of LIS under both operations with worst-case update time ~O(n^ϵ), for any constant ϵ>0. We exponentially improve on their result by designing an algorithm that maintains a (1+ϵ)-approximation of LIS under both operations with worst-case update time ~O(ϵ^(−5)). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.

While this essentially settles the complexity of the approximate version of the problem, the exact version seems more elusive. The only known sublinear solution was given very recently by Kociumaka and Seddighin [STOC 2021] and takes ~O(n^(2/3)) time per update. We show polynomial conditional lower bounds for two natural extensions of this problem: weighted LIS and LIS in any subarray.

Joint work with Wojciech Janczewski.