10 citations · 19 across the 9 of their papers we have counts for
15 papers
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…
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…
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…
A New Approach to Enumerating Statistics Modulo
William Kuszmaul
We find a new approach to computing the remainder of a polynomial modulo ; such a computation is called modular enumeration. Given a polynomial with coefficients from a comm…
New Results on Doubly Adjacent Pattern-Replacement Equivalences
William Kuszmaul
In this paper, we consider the family of pattern-replacement equivalence relations referred to as the "indices and values adjacent" case. Each such equivalence is determined by a p…
Equivalence Classes in for Three Families of Pattern-Replacement Relations
William Kuszmaul, Ziling Zhou
We study a family of equivalence relations on , the group of permutations on letters, created in a manner similar to that of the Knuth relation and the forgotten relation.…
Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns
William Kuszmaul
We study a family of equivalence relations on , the group of permutations on letters, created in a manner similar to that of the Knuth relation and the forgotten relation.…