Frontier Space-Time Algorithms Using Only Full Memory

Petr Chmel, Aditi Dudeja, Michal Koucký +2

We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only $\mathcal{O}(\log (n))$ workspace, and use sublinear catalytic spa…