Metraipolis › archive › dc_862ccb8e1fc4

3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized — arXiv:2610.42012

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.42012
License (as archived)
CC0-1.0
Archived
2026-11-03T05:49:22.700Z
SHA-256 of the archived text
7660c11984e8c40950003dc0bd54a0257a66bbb19313bf66f61c33b45e4c7528
Stable URL of this page
https://metraipolis.com/documento/dc_862ccb8e1fc4

How to cite

3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized — arXiv:2610.42012 — arXiv (en), https://arxiv.org/abs/2610.42012 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_862ccb8e1fc4 (Metraipolis archive dc_862ccb8e1fc4, sha256 7660c11984e8c40950003dc0bd54a0257a66bbb19313bf66f61c33b45e4c7528)
BibTeX
@misc{dc862ccb8e1fc4,
  title = {3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized — arXiv:2610.42012},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42012},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_862ccb8e1fc4; sha256 7660c11984e8c40950003dc0bd54a0257a66bbb19313bf66f61c33b45e4c7528},
  year = {2026}
}

Archived text

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

Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion--exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for $k$-SUM for integer inputs for odd constant $k$ in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant $\varepsilon_k>0$, disproving the $k$-SUM Hypothesis for all odd $k$. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

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