Fast and Simple Modular Subset Sum

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