论文标题
快速，简单的模块化子集总和
Fast and Simple Modular Subset Sum
论文作者
论文摘要
我们对某些给定整数$ m $的有限循环组$ \ mathbb {z} _m $重新访问子集总和问题。在强大的指数时间假设下，最近的一系列工作为此问题提供了近乎最佳的算法。 Koiliaris和Xu（Soda'17，Talg'19）给出了一种确定性的算法，随着时间的推移运行$ \ tilde {o}（M^{5/4}）$，后来将其提高到Axiotis等人。 （Soda'19）。 在这项工作中，我们提出了两种简单的算法，用于在$ m $中以接近线性的时间运行的模块子集总和问题，既可以有效地在$ \ m athbb {z} _m $上实现Bellman的迭代。第一个是在时间$ o（m \ log^2 m）$中运行的随机算法，该算法仅基于滚动哈希和前缀总和的基本数据结构；为了说明其简单性，我们提供了Python中该算法的简短实施。我们的第二个解决方案是在时间$ o（m \ \ mathrm {polylog} \ m）$中运行的确定性算法，该算法使用动态数据结构进行字符串操作。 我们进一步表明，这项工作中开发的技术还可以导致所有对无方向图上的所有对非降低路径问题（APNP）的简单算法，从而匹配了$ \ tilde {o} {o}（o}（n^2）$的近乎最佳运行时间。 （ICALP'19）。
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 (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 time by Axiotis et al. (SODA'19). In this work, we present two simple algorithms for the Modular Subset Sum problem running in near-linear time in $m$, both efficiently implementing Bellman's 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. (ICALP'19).
