Metraipolis › archive › dc_8fa101214a4e

Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time — arXiv:2610.22133

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.22133
License (as archived): CC0-1.0
Archived: 2026-10-16T10:40:26.786Z
SHA-256 of the archived text: 75ea4343af353fadfe3cf063cf247ee5a3029289e2f52c7406ff59cc917b5249
Stable URL of this page: https://metraipolis.com/documento/dc_8fa101214a4e

How to cite

Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time — arXiv:2610.22133 — arXiv (en), https://arxiv.org/abs/2610.22133 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8fa101214a4e (Metraipolis archive dc_8fa101214a4e, sha256 75ea4343af353fadfe3cf063cf247ee5a3029289e2f52c7406ff59cc917b5249)

BibTeX

@misc{dc8fa101214a4e,
  title = {Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time — arXiv:2610.22133},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.22133},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8fa101214a4e; sha256 75ea4343af353fadfe3cf063cf247ee5a3029289e2f52c7406ff59cc917b5249},
  year = {2026}
}

Archived text

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

In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained complexity, both from the upper- and lower-bound side: * From the upper-bound side, for each of these problems the authors give an intermediate running time strictly between $n^{\omega}$ and $n^3$, where $\omega<2.371177$ is the matrix multiplication exponent. When optimized, this running time can be made $\tilde{\mathcal{O}}(n^{(3+\omega)/2})$. By now, many more problems can be solved in this running time: directed unweighted or node-weighted APSP, a variety of matrix products such as max-min and dominance, RNA Folding and many more. For some of these, the community has also developed tools suggesting that this intermediate running time is necessary. * From the lower-bound side, the authors give lower bounds of $n^{\omega-o(1)}$, conditioned on three natural hardness hypotheses on the complexity of quantified variants of triangle detection that account for different types of hardness of such problems. Despite this, it has remained open for over 20 years which of these two pieces of evidence reflects the truth for the problems that Kratsch and Spinrad study: whether the intermediate running time is indeed necessary and stronger lower bounds hold, or whether the hardness evidence of Kratsch and Spinrad is essentially tight. In this paper, we resolve this question and show that the latter is the case: all problems admit an $\tilde{\mathcal{O}}(n^{\omega})$ time algorithm. As an additional contribution, we make partial algorithmic progress on further problems in structural graph theory of intermediate complexity, improving over previous work [Chiu and Lu, STACS 2022 and Information and Computation 2024][Spinrad, Discrete Applied Math 2004].

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.22133 — 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-10-16T08:53:17.678Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).