Metraipolis › archive › dc_60da0d88017d

Deterministic Linear-Time Modular Subset Sum — arXiv:2609.30992

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.30992
License (as archived)
CC0-1.0
Archived
2026-10-08T03:35:13.480Z
SHA-256 of the archived text
7f79bd80bd2e7473a0af9d804cc03e2cf6af2291ad9cec62a097c32c46730570
Stable URL of this page
https://metraipolis.com/documento/dc_60da0d88017d

How to cite

Deterministic Linear-Time Modular Subset Sum — arXiv:2609.30992 — arXiv (en), https://arxiv.org/abs/2609.30992 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_60da0d88017d (Metraipolis archive dc_60da0d88017d, sha256 7f79bd80bd2e7473a0af9d804cc03e2cf6af2291ad9cec62a097c32c46730570)
BibTeX
@misc{dc60da0d88017d,
  title = {Deterministic Linear-Time Modular Subset Sum — arXiv:2609.30992},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30992},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_60da0d88017d; sha256 7f79bd80bd2e7473a0af9d804cc03e2cf6af2291ad9cec62a097c32c46730570},
  year = {2026}
}

Archived text

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

We give a deterministic $O(m)$-time algorithm for exact modular subset sum over every modulus $m$ on compact input: distinct residues with multiplicities. It reports all reachable residues and answers one target query, returning a witness when the target is reachable. The algorithm uses $O(m)$ auxiliary words on an arithmetic word-RAM. This improves Potępa's deterministic $O(m\log m\alpha(m))$-time bound under the same input convention. The running time matches the cost of explicitly reporting all $m$ reachability bits. We represent reachable residues as runs along cycles of repeated addition. Newly reached residues pay for scans of partial runs, and processing prime factors in increasing order makes cycle rebuilding linear. A theorem on subset sums of distinct units limits the number of adaptive boundary batches to $O(m^{3/4})$; radix sorting their $O(m)$ total keys also takes $O(m)$ time.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.30992 — 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-08T03:12:28.085Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).