research
∙
10/08/2022
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
Modern hash table designs strive to minimize space while maximizing spee...
share
research
∙
09/17/2022
A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem
In the d-dimensional cow-path problem, a cow living in ℝ^d must locate a...
research
∙
09/13/2022
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
This paper considers the basic question of how strong of a probabilistic...
research
∙
07/21/2022
Tight Bounds for Monotone Minimal Perfect Hashing
The monotone minimal perfect hash function (MMPHF) problem is the follow...
research
∙
07/02/2022
Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
Dynamic Time Warping (DTW) is a widely used similarity measure for compa...
research
∙
05/13/2022
Balanced Allocations: The Heavily Loaded Case with Deletions
In the 2-choice allocation problem, m balls are placed into n bins, and ...
research
∙
05/03/2022
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
The p-processor cup game is a classic and widely studied scheduling prob...
research
∙
03/05/2022
Online List Labeling: Breaking the log^2n Barrier
The online list labeling problem is an algorithmic primitive with a larg...
research
∙
01/05/2022
What Does Dynamic Optimality Mean in External Memory?
In this paper, we revisit the question of how the dynamic optimality of ...
research
∙
11/24/2021
Tiny Pointers
This paper introduces a new data-structural object that we call the tiny...
research
∙
11/14/2021
Stochastic and Worst-Case Generalized Sorting Revisited
The generalized sorting problem is a restricted version of standard comp...
research
∙
10/31/2021
On the Optimal Time/Space Tradeoff for Hash Tables
For nearly six decades, the central open question in the study of hash t...
research
∙
09/09/2021
All-Purpose Hashing
Despite being one of the oldest data structures in computer science, has...
research
∙
07/05/2021
Incremental Edge Orientation in Forests
For any forest G = (V, E) it is possible to orient the edges E so that n...
research
∙
07/02/2021
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering
First introduced in 1954, linear probing is one of the oldest data struc...
research
∙
04/12/2021
How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games
The cup game on n cups is a multi-step game with two players, a filler a...
research
∙
02/09/2021
The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
Azuma's inequality is a tool for proving concentration bounds on random ...
research
∙
01/04/2021
Binary Dynamic Time Warping in Linear Time
Dynamic time warping distance (DTW) is a widely used distance measure be...
research
∙
12/01/2020
Train Tracks with Gaps: Applying the Probabilistic Method to Trains
We identify a tradeoff curve between the number of wheels on a train car...
research
∙
11/30/2020
The Variable-Processor Cup Game
The problem of scheduling tasks on p processors so that no task ever get...
research
∙
08/24/2020
Algorithms and Lower Bounds for the Worker-Task Assignment Problem
We study the problem of assigning workers to tasks where each task has d...
research
∙
04/27/2020
In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory: An In-Place Algorithm With Provably Optimal Cache Behavior
We present an in-place algorithm for the parallel partition problem that...
research
∙
04/17/2020
Contention Resolution Without Collision Detection
This paper focuses on the contention resolution problem on a shared comm...
research
∙
10/29/2019
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game
In each step of the p-processor cup game on n cups, a filler distributes...
research
∙
10/27/2019
Cilkmem: Algorithms for Analyzing the Memory High-Water Mark of Fork-Join Parallel Programs
Software engineers designing recursive fork-join programs destined to ru...
research
∙
04/22/2019
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
Dynamic time warping distance (DTW) is a widely used distance measure be...
research
∙
04/05/2019
Achieving Optimal Backlog in Multi-Processor Cup Games
The single- and multi- processor cup games can be used to model natural ...
research
∙
03/08/2019
The One-Way Communication Complexity of Dynamic Time Warping Distance
We resolve the randomized one-way communication complexity of Dynamic Ti...
research
∙
11/10/2018
Efficiently Approximating Edit Distance Between Pseudorandom Strings
We present an algorithm for approximating the edit distance ed(x, y) bet...
research
∙
04/26/2018