论文标题
更快的确定性模块集总和
Faster Deterministic Modular Subset Sum
论文作者
论文摘要
我们考虑模块化子集总和问题：从$ \ mathbb {z} _m $和目标整数$ t $中给定一个多键$ x $的整数，请确定是否存在$ x $的子集，总和等于$ t \ pmod {m} $。 Cardinal和Iacono（Sosa'21）以及Axiotis等人的最新独立作品。 （SOSA'21）为此问题提供了简单且近线性的算法。红衣主教和IACONO给出了一种随机算法，该算法以$ O（M \ log M）$时间运行，而Axiotis等人。给出了一种确定性算法，该算法在$ O（M \ text {polylog} m）$ time中运行。两种结果都通过还原到文本问题来起作用，该问题是使用动态字符串数据结构来解决的。 在这项工作中，我们开发了一个简单的数据结构，专门旨在处理模块化子集算法中出现的文本问题。我们称为Shift-Tree的数据结构是段树的简单变体。我们既提供基于哈希的转变的基于哈希的和确定性的变体。 然后，我们将数据结构应用于模块集子集总和问题，并获得两种算法。第一种算法是蒙特卡洛随机分组，与Cardinal和iacono的Las-Vegas算法的$ O（M \ log M）$运行时匹配。第二算法是完全确定性的，并以$ O（M \ log M \cdotα（m））$时间运行，其中$α$是倒数的ackermann函数。
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 \pmod{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 α(m))$ time, where $α$ is the inverse Ackermann function.
