10 citations · 10 across the 3 of their papers we have counts for
9 papers
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…
Train Tracks with Gaps: Applying the Probabilistic Method to Trains
William Kuszmaul
We identify a tradeoff curve between the number of wheels on a train car, and the amount of track that must be installed in order to ensure that the train car is supported by the t…
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…