8 papers
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…
The Structure of In-Place Space-Bounded Computation
James Cook, Surendra Ghentiyala, Ian Mertz +2
In the standard model of computing multi-output functions in logspace (), we are given a read-only tape holding and a logarithmic length worktape, and must print $…
Graphs With the Same Edge Count in Each Neighborhood
Nathan S. Sheffield, Zoe Xi
In a recent paper, Caro, Lauri, Mifsud, Yuster, and Zarb ask which parameters and admit the existence of an -regular graph such that the neighborhood of each vertex indu…
New Bounds for Induced Turán Problems
Nathan S. Sheffield
In a recent paper, Hunter, Milojević, Sudakov and Tomon consider the maximum number of edges in an -vertex graph containing no copy of the complete bipartite graph and…
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…
Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
Brian Liu, Nathan S. Sheffield, Alek Westover
We study the following generalization of the Hamiltonian cycle problem: Given integers and graph , does there exist a closed walk in that visits every vertex at least…
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…