4 papers · 1 filter
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Adelmo Morrison Orozco, Nathan Sheffield, Ryan Williams
We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computati…
The Limits of Black-Box Reductions for All-Pairs Triangle Detection
Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi
For any tripartite relation , the -Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R…
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…