research
∙
02/22/2023
RNA secondary structures: from ab initio prediction to better compression, and back
In this paper, we use the biological domain knowledge incorporated into ...
share
research
∙
09/14/2022
Multiway Powersort
Powersort (Munro Wild, ESA2018) has recently replaced Timsort's subo...
research
∙
11/05/2021
Randomized Communication and the Implicit Graph Conjecture
The most basic lower-bound question in randomized communication complexi...
research
∙
11/02/2021
Towards the 5/6-Density Conjecture of Pinwheel Scheduling
Pinwheel Scheduling aims to find a perpetual schedule for unit-length ta...
research
∙
04/27/2021
Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures
We present a new universal source code for unlabeled binary and ordinal ...
research
∙
10/17/2020
Lazy Search Trees
We introduce the lazy search tree data structure. The lazy search tree i...
research
∙
10/08/2020
Succinct Permutation Graphs
We present a succinct, i.e., asymptotically space-optimal, data structur...
research
∙
05/15/2020
Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs
We present the first succinct data structure for ordinal trees that supp...
research
∙
08/01/2019
Dynamic Optimality Refuted -- For Tournament Heaps
We prove a separation between offline and online algorithms for finger-b...
research
∙
05/06/2019
Efficient Second-Order Shape-Constrained Function Fitting
We give an algorithm to compute a one-dimensional shape-constrained func...
research
∙
03/06/2019
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
The range-minimum query (RMQ) problem is a fundamental data structuring ...
research
∙
11/03/2018
QuickXsort - A Fast Sorting Scheme in Theory and Practice
QuickXsort is a highly efficient in-place sequential sorting scheme that...
research
∙
10/29/2018
Sesquickselect: One and a half pivots for cache-efficient selection
Because of unmatched improvements in CPU performance, memory transfers h...
research
∙
05/10/2018
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
We present two stable mergesort variants, "peeksort" and "powersort", th...
research
∙
03/15/2018