2026-07-23T20:14:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27071 2026-07-23T11:36:19Z ddc:004 open_access

Frontier Space-Time Algorithms Using Only Full Memory Chmel, Petr Dudeja, Aditi Koucký, Michal Mertz, Ian Rajgopal, Ninad Catalytic computation Connectivity Edit distance Discrete Fréchet distance We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only 𝒪(log(n)) workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed s-t connectivity using n / 2^{Θ(√{log n})} catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [James Cook and Edward Pyne, 2026]. Furthermore, using only 𝒪(log(n)) random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Fréchet Distance, again using n / 2^{Θ(√{log n})} catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Chmel and Aditi Dudeja and Michal Koucký and Ian Mertz and Ninad Rajgopal 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.29 urn:nbn:de:0030-drops-270710 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.29 eng https://creativecommons.org/licenses/by/4.0/legalcode