We revisit the Subset Sum problem over the finite cyclic group $mathbb{Z}_m$ for some given integer $m$. A series of recent works has provided near-optimal algorithms for this problem under the Strong Exponential Time Hypothesis. Koiliaris and Xu (SODA17, TALG19) gave a deterministic algorithm running in time $tilde{O}(m^{5/4})$, which was later improved to $O(m log^7 m)$ randomized time by Axiotis et al. (SODA19). In this work, we present two simple algorithms for the Modular Subset Sum problem running in near-linear time in $m$, both efficiently implementing Bellmans iteration over $mathbb{Z}_m$. The first one is a randomized algorithm running in time $O(m log^2 m)$, that is based solely on rolling hash and an elementary data-structure for prefix sums; to illustrate its simplicity we provide a short and efficient implementation of the algorithm in Python. Our second solution is a deterministic algorithm running in time $O(m mathrm{polylog} m)$, that uses dynamic data structures for string manipulation. We further show that the techniques developed in this work can also lead to simple algorithms for the All Pairs Non-Decreasing Paths Problem (APNP) on undirected graphs, matching the near-optimal running time of $tilde{O}(n^2)$ provided in the recent work of Duan et al. (ICALP19).
Download