Metraipolis › archive › dc_cc4e7968252f

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-03T05:49:25.706Z
SHA-256 of the archived text: d06bba34038a99e321b77f854472106638e15eee69cb2aea021e8bf36744f440
Stable URL of this page: https://metraipolis.com/documento/dc_cc4e7968252f

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_cc4e7968252f (Metraipolis archive dc_cc4e7968252f, sha256 d06bba34038a99e321b77f854472106638e15eee69cb2aea021e8bf36744f440)

BibTeX

@misc{dccc4e7968252f,
  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_cc4e7968252f; sha256 d06bba34038a99e321b77f854472106638e15eee69cb2aea021e8bf36744f440},
  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-03T05:34:47.029Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).