Frontier Space-Time Algorithms Using Only Full Memory
Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal · 2026
Read Frontier Space-Time Algorithms Using Only Full Memory by Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-21089.txt.
Description
Catalytic methods promise small workspace with lent memory, but matching the best non-catalytic bounds in poly-time has been elusive. Petr Chmel, Aditi Dudeja, Michal Koucky, Ian Mertz, and Ninad Rajgopal achieve it in this 2026 arXiv paper. Their arrow-link method runs in poly-time with log-size workspace and below-linear catalytic space, matching state-of-the-art non-catalytic bounds.
A coin-flip variant using only log-size many random bits nearly matches the fastest free-space time bounds. The same catalytic budget also covers edit distance, longest shared run, and discrete Frechet distance in poly-time. The work pushes catalytic work onto the frontier before held by plain space-bounded methods.
Catalog record
| CREATOR | Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 734 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-21089