Faster Deterministic Modular Subset Sum

Abstract

We consider the Modular Subset Sum problem: given a multiset $X$ of integers from ${\mathbb{Z}}_m$ and a target integer $t$, decide if there exists a subset of $X$ with a sum equal to $t(\mathrm{mod}m)$. Recent independent works by Cardinal and Iacono (SOSA'21), and Axiotis et al. (SOSA'21) provided simple and near-linear algorithms for this problem. Cardinal and Iacono gave a randomized algorithm that runs in $O(m\log m)$ time, while Axiotis et al. gave a deterministic algorithm that runs in $O(m\text{ polylog }m)$ time. Both results work by reduction to a text problem, which is solved using a dynamic strings data structure. In this work, we develop a simple data structure, designed specifically to handle the text problem that arises in the algorithms for Modular Subset Sum. Our data structure, which we call the shift-tree, is a simple variant of a segment tree. We provide both a hashing-based and a deterministic variant of the shift-trees. We then apply our data structure to the Modular Subset Sum problem and obtain two algorithms. The first algorithm is Monte-Carlo randomized and matches the $O(m\log m)$ runtime of the Las-Vegas algorithm by Cardinal and Iacono. The second algorithm is fully deterministic and runs in $O(m\log m\cdot \alpha (m))$ time, where $\alpha$ is the inverse Ackermann function.

16 pages, accepted at ESA 2021

References in corpus (1)

• Fast and Simple Modular Subset Sum

Cited by in corpus (1)

• Knapsack and Subset Sum with Small Items