8 papers · 1 filter
Lower Bounds for Linear Hashing via Arithmetic Kakeya
Ainesh Bakshi, Alex Conway, Hanna Komlós +2
Affine modular linear hashing is one of the simplest classical hash families. For a prime , the hash function is obtained by choosing uniformly from and…
Listing 6-Cycles in Sparse Graphs
Virginia Vassilevska Williams, Alek Westover
This work considers the problem of output-sensitive listing of occurrences of -cycles for fixed constant in an undirected host graph with edges and -cycle…
When to Give Up on a Parallel Implementation
Nathan S. Sheffield, Alek Westover
In the Serial Parallel Decision Problem (SPDP), introduced by Kuszmaul and Westover [SPAA'24], an algorithm receives a series of tasks online, and must choose for each between a se…
A Nearly Quadratic Improvement for Memory Reallocation
Martin Farach-Colton, William Kuszmaul, Nathan Sheffield +1
In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the…
Scheduling Jobs with Work-Inefficient Parallel Solutions
William Kuszmaul, Alek Westover
This paper introduces the \emph{serial-parallel decision problem}. Consider an online scheduler that receives a series of tasks, where each task has both a parallel and a serial im…
On the Relationship Between Several Variants of the Linear Hashing Conjecture
Alek Westover
In Linear Hashing () with bins on a size universe , items are placed in bins by…
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…