arXiv preprint ·
Deterministic Linear-Time Modular Subset Sum
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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α(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.