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…