Showing 2026Show all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…