Metraipolis › archive › dc_b17958affeb2

Catalytic space-efficient algorithms for Distance and Determinant — arXiv:2610.41723

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41723
License (as archived)
CC0-1.0
Archived
2026-11-02T08:06:48.944Z
SHA-256 of the archived text
2595181496bf3de917d93f96f0584991d8385eb2f24fa2af8c66cd4dd9429982
Stable URL of this page
https://metraipolis.com/documento/dc_b17958affeb2

How to cite

Catalytic space-efficient algorithms for Distance and Determinant — arXiv:2610.41723 — arXiv (en), https://arxiv.org/abs/2610.41723 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b17958affeb2 (Metraipolis archive dc_b17958affeb2, sha256 2595181496bf3de917d93f96f0584991d8385eb2f24fa2af8c66cd4dd9429982)
BibTeX
@misc{dcb17958affeb2,
  title = {Catalytic space-efficient algorithms for Distance and Determinant — arXiv:2610.41723},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41723},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b17958affeb2; sha256 2595181496bf3de917d93f96f0584991d8385eb2f24fa2af8c66cd4dd9429982},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41723. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Catalytic computation reuses potentially large but in-use space (or catalytic space) which must be restored to its initial contents while the clean space is small. This allows all problems in $\mathsf{NL}$ and even larger classes to be in catalytic logspace [Buhrman et al, STOC2014]. In [Chmel et al, CCC2026] the catalytic space for reachability was restricted to sublinear space (specifically, $n \big/ 2^{\theta(\sqrt{\log n})}$ space) while remaining in polynomial time. This matches the non-catalytic bounds from [Barnes et al, SICOMP1998]. We extend the reachability bound to shortest distance, proving a simultaneous sublinear catalytic space and polynomial time bound (henceforth called, sublinear $\mathsf{CLP}$). This is the first simultaneous sublinear space and polynomial time bound for distance even without the catalytic discipline. Moreover, our bound works even for polynomially weighted graphs. Along the way we prove simultaneous near linear catalytic space ($\mathcal{O}(n\log^{O(1)}{n})$) and polynomial time bounds for the determinant. We also show some applications to planar matching problems. Our starting point was catalytic computation of reachability in directed graphs by [Cook-Pyne, ITCS2026]. [Edenhofer, arXiv:2602.21088 ] used it to give a tradeoff between catalytic and non-catalytic space, while [Chmel et al, CCC2026] compress the graph to a smaller graph preserving $s,t$-reachability to achieve a smaller space bound. All three can be modified to yield an algorithm for unweighted distance. Our contribution is to define an approximation to the walk polynomial in weighted graphs that allows us to infer weighted $s,t$-distance in sublinear $\mathsf{CLP}$. We do so by non-trivially combining elements from each of the above three papers.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41723 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:45:15.789Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).