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

CREATORPetr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE734 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-21089

Browse the full library · About the Tower of Babel