6 citations · 9 across the 4 of their papers we have counts for
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.CC2026
A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira +1
In this work, we propose a new bounded arithmetic theory, denoted , designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer scie…