10 citations · 19 across the 9 of their papers we have counts for
10 papers · 1 filter
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
William Kuszmaul, Shyam Narayanan
The \emph{-processor cup game} is a classic and widely studied scheduling problem that captures the setting in which a -processor machine must assign tasks to processors ove…
Stochastic and Worst-Case Generalized Sorting Revisited
William Kuszmaul, Shyam Narayanan
The \emph{generalized sorting problem} is a restricted version of standard comparison sorting where we wish to sort elements but only a subset of pairs are allowed to be compar…
How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games
William Kuszmaul
The cup game on cups is a multi-step game with two players, a filler and an emptier. At each step, the filler distributes unit of water among the cups, and then the emptier…
Binary Dynamic Time Warping in Linear Time
William Kuszmaul
Dynamic time warping distance (DTW) is a widely used distance measure between time series . It was shown by Abboud, Backurs, and Williams that in the \emph{binary cas…
The Variable-Processor Cup Game
William Kuszmaul, Alek Westover
The problem of scheduling tasks on processors so that no task ever gets too far behind is often described as a game with cups and water. In the -processor cup game on cu…
In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory
William Kuszmaul, Alek Westover
We present an in-place algorithm for the partition problem that has linear work and polylogarithmic span. The algorithm uses only exclusive read/write shared variables, and can be…
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game
William Kuszmaul
In each step of the -processor cup game on cups, a filler distributes up to units of water among the cups, subject only to the constraint that no cup receives more than…
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
William Kuszmaul
Dynamic time warping distance (DTW) is a widely used distance measure between time series. The best known algorithms for computing DTW run in near quadratic time, and conditional l…
Achieving Optimal Backlog in Multi-Processor Cup Games
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
The single- and multi- processor cup games can be used to model natural problems in areas such as processor scheduling, deamortization, and buffer management. At the beginning of t…
Efficiently Approximating Edit Distance Between Pseudorandom Strings
William Kuszmaul
We present an algorithm for approximating the edit distance between two strings and in time parameterized by the degree to which one of the string…