{"ID":2822808,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.01390","arxiv_id":"2601.01390","title":"Derandomizing Pseudopolynomial Algorithms for Subset Sum","abstract":"We reexamine the classical subset sum problem: given a set $X$ of $n$ positive integers and a number $t$, decide whether there exists a subset of $X$ that sums to $t$; or more generally, compute the set $\\mbox{out}$ of all numbers $y\\in\\{0,\\ldots,t\\}$ for which there exists a subset of $X$ that sums to $y$. Standard dynamic programming solves the problem in $O(tn)$ time. In SODA'17, two papers appeared giving the current best deterministic and randomized algorithms, ignoring polylogarithmic factors: Koiliaris and Xu's deterministic algorithm runs in $\\widetilde{O}(t\\sqrt{n})$ time, while Bringmann's randomized algorithm runs in $\\widetilde{O}(t)$ time. We present the first deterministic algorithm running in $\\widetilde{O}(t)$ time. Our technique has a number of other applications: for example, we can also derandomize the more recent output-sensitive algorithms by Bringmann and Nakos [STOC'20] and Bringmann, Fischer, and Nakos [SODA'25] running in $\\widetilde{O}(|\\mbox{out}|^{4/3})$ and $\\widetilde{O}(|\\mbox{out}|\\sqrt{n})$ time, and we can derandomize a previous fine-grained reduction from 0-1 knapsack to min-plus convolution by Cygan et al. [ICALP'17].","short_abstract":"We reexamine the classical subset sum problem: given a set $X$ of $n$ positive integers and a number $t$, decide whether there exists a subset of $X$ that sums to $t$; or more generally, compute the set $\\mbox{out}$ of all numbers $y\\in\\{0,\\ldots,t\\}$ for which there exists a subset of $X$ that sums to $y$. Standard dy...","url_abs":"https://arxiv.org/abs/2601.01390","url_pdf":"https://arxiv.org/pdf/2601.01390v1","authors":"[\"Timothy M. Chan\"]","published":"2026-01-04T06:07:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}