DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.29

Frontier Space-Time Algorithms Using Only Full Memory

Authors: Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, and Ninad Rajgopal

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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].

Cite as

Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, and Ninad Rajgopal. Frontier Space-Time Algorithms Using Only Full Memory. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chmel_et_al:LIPIcs.CCC.2026.29,
  author =	{Chmel, Petr and Dudeja, Aditi and Kouck\'{y}, Michal and Mertz, Ian and Rajgopal, Ninad},
  title =	{{Frontier Space-Time Algorithms Using Only Full Memory}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{29:1--29:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.29},
  URN =		{urn:nbn:de:0030-drops-270710},
  doi =		{10.4230/LIPIcs.CCC.2026.29},
  annote =	{Keywords: Catalytic computation, Connectivity, Edit distance, Discrete Fr\'{e}chet distance}
}

Search Results

Documents authored by Chmel, Petr

Frontier Space-Time Algorithms Using Only Full Memory

Abstract

Cite as

Thanks for your feedback!

Could not send message