Metraipolis › archive › dc_b098701ecf70

Real-to-Integer Reduction for All-Pairs Shortest Paths — arXiv:2611.04847

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04847
License (as archived)
CC0-1.0
Archived
2026-11-04T19:07:38.661Z
SHA-256 of the archived text
b3ad5039a8035685a3a572adb67452f90398cf58a782eadc29d1afb47b9a3eac
Stable URL of this page
https://metraipolis.com/documento/dc_b098701ecf70

How to cite

Real-to-Integer Reduction for All-Pairs Shortest Paths — arXiv:2611.04847 — arXiv (en), https://arxiv.org/abs/2611.04847 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b098701ecf70 (Metraipolis archive dc_b098701ecf70, sha256 b3ad5039a8035685a3a572adb67452f90398cf58a782eadc29d1afb47b9a3eac)
BibTeX
@misc{dcb098701ecf70,
  title = {Real-to-Integer Reduction for All-Pairs Shortest Paths — arXiv:2611.04847},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04847},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b098701ecf70; sha256 b3ad5039a8035685a3a572adb67452f90398cf58a782eadc29d1afb47b9a3eac},
  year = {2026}
}

Archived text

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

Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current techniques, or are the real-valued variants inherently harder? One way to study this question is through real-to-integer reductions. We give (randomized, combinatorial) subcubic real-to-integer reductions for two central graph problems in fine-grained complexity: All-Pairs Shortest Paths and Exact Triangle. That is, we show that if the integer variants of these problems can be solved in truly subcubic time, then the real variants can also be solved in truly subcubic time. Our work extends and combines techniques from three previous works: (1) our real-to-integer reduction for the 3SUM problem (Fischer, Polak, Schmidt, FOCS 2026), which itself combines the Frank--Tardos theorem from optimization with Freiman's theorem from additive combinatorics; (2) universe reduction for APSP (Fischer, STOC 2026), which we generalize to reals and use to reduce the doubling of the set of edge weights; and (3) the ``Fredman's trick meets dominance product'' technique (Chan, Vassilevska Williams, Xu, STOC 2023), which is needed to adapt the prior real-to-integer framework from equality constraints to inequalities. As a corollary, our reduction combined with Yuval's fast Integer APSP algorithm in the real RAM model with multiplication (IPL 1976) shows that the Real APSP Hypothesis is false in this model, which also follows from the very recent breakthrough by Alman and Vassilevska Williams using a very different approach.

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/2611.04847 — 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-04T18:40:52.466Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).