2026-08-17T05:20:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10043 2024-03-06T10:30:34Z ddc:004 open_access

A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum Jin, Ce Wu, Hongxun subset sum formal power series FFT Given a multiset S of n positive integers and a target integer t, the Subset Sum problem asks to determine whether there exists a subset of S that sums up to t. The current best deterministic algorithm, by Koiliaris and Xu [SODA'17], runs in O~(sqrt{n}t) time, where O~ hides poly-logarithm factors. Bringmann [SODA'17] later gave a randomized O~(n + t) time algorithm using two-stage color-coding. The O~(n+t) running time is believed to be near-optimal. In this paper, we present a simple and elegant randomized algorithm for Subset Sum in O~(n + t) time. Our new algorithm actually solves its counting version modulo prime p>t, by manipulating generating functions using FFT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ce Jin and Hongxun Wu 2019 Is Part Of OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2019.17 urn:nbn:de:0030-drops-100436 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.17 eng https://creativecommons.org/licenses/by/3.0/legalcode