Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Conditional Lower Bounds for Variants of Dynamic LIS   In this note, we consider the complexity of maintaining the longest
increasing subsequence (LIS) of an array under (i) inserting an element, and
(ii) deleting an element of an array. We show that no algorithm can support
queries and updates in time $\mathcal{O}(n^{1/2-\epsilon})$ and
$\mathcal{O}(n^{1/3-\epsilon})$ for the dynamic LIS problem, for any constant
$\epsilon>0$, when the elements are weighted or the algorithm supports
1D-queries (on subarrays), respectively, assuming the All-Pairs Shortest Paths
(APSP) conjecture or the Online Boolean Matrix-Vector Multiplication (OMv)
conjecture. The main idea in our construction comes from the work of Abboud and
Dahlgaard [FOCS 2016], who proved conditional lower bounds for dynamic planar
graph algorithm. However, this needs to be appropriately adjusted and
translated to obtain an instance of the dynamic LIS problem.

17
The categories of this paper are: q-fin
2
The categories of this paper are: math
24
The categories of this paper are: dg-ga
30
The categories of this paper are: q-alg
6
The categories of this paper are: astro-ph
22
The categories of this paper are: chao-dyn
21
The categories of this paper are: adap-org
23
The categories of this paper are: solv-int
7
The categories of this paper are: hep-th
19
The categories of this paper are: eess
16
The categories of this paper are: stat
32
The categories of this paper are: atom-ph
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph