Derandomizing Pseudopolynomial Algorithms for Subset Sum

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].

No reviews yet.

No comments yet.