The predecessor problem is a key component of the fundamental sorting-and-searching
core of algorithmic problems. While binary search is the optimal solution in the comparison …

The suffix array SA [1.. n] of a text T of length n is a permutation of {1,…, n} describing the
lexicographical ordering of suffixes of T and is considered to be one of the most important …

In this paper, we study the fundamental problem of maintaining a dynamic collection of
strings under the following operations:• make_string–add a string of constant length,• concat …

A growing line of work shows how learned predictions can be used to break through worst-
case barriers to improve the running time of an algorithm. However, incorporating …

We consider finding a pattern of length mm in a compacted (linear-size) trie storing strings
over an alphabet of size σ σ. In static tries, we achieve O (m+\lg\lg σ) O (m+ lg lg σ) …

The online list-labeling problem is an algorithmic primitive with a large literature of upper
bounds, lower bounds, and applications. The goal is to store a dynamically changing set of …

We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range
reporting. We present a new data structure achieving $ O\left (\frac {\log n}{\log\log n}+ …

Many problems in processor scheduling, deamortization, and buffer management can be
modeled as single-and multi-processor cup games. At the beginning of the single-processor …

In each step of the cup game on n cups, a filler distributes up to 1–∊ water among the cups,
and then an emptier removes 1 unit of water from a single cup. The emptier's goal is to …

We consider the problem of storing a dynamic string S over an alphabet Σ={1,…, σ} in
compressed form. Our representation supports insertions and deletions of symbols and …