Frontier Space-Time Algorithms Using Only Full Memory
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918353856102400 |
|---|---|
| author | Chmel, Petr Dudeja, Aditi Koucký, Michal Mertz, Ian Rajgopal, Ninad |
| author_facet | Chmel, Petr Dudeja, Aditi Koucký, Michal Mertz, Ian Rajgopal, Ninad |
| contents | 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 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 \big/ 2^{Θ(\sqrt{\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 [Cook and Pyne, 2026]. Furthermore, using only $\mathcal{O}(\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 \big/ 2^{Θ(\sqrt{\log n})}$ catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21089 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Frontier Space-Time Algorithms Using Only Full Memory Chmel, Petr Dudeja, Aditi Koucký, Michal Mertz, Ian Rajgopal, Ninad Data Structures and Algorithms Computational Complexity 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 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 \big/ 2^{Θ(\sqrt{\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 [Cook and Pyne, 2026]. Furthermore, using only $\mathcal{O}(\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 \big/ 2^{Θ(\sqrt{\log n})}$ catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021]. |
| title | Frontier Space-Time Algorithms Using Only Full Memory |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2602.21089 |