2026-07-23T07:57:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14657 2024-03-06T10:54:33Z ddc:004 open_access

Faster Deterministic Modular Subset Sum Potępa, Krzysztof Modular Subset Sum String Problem Segment Tree Data Structure We consider the Modular Subset Sum problem: given a multiset X of integers from ℤ_m and a target integer t, decide if there exists a subset of X with a sum equal to t (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 𝒪(m log m) time, while Axiotis et al. gave a deterministic algorithm that runs in 𝒪(m 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 𝒪(m log m) runtime of the Las-Vegas algorithm by Cardinal and Iacono. The second algorithm is fully deterministic and runs in 𝒪(m log m ⋅ α(m)) time, where α is the inverse Ackermann function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Krzysztof Potępa 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.76 urn:nbn:de:0030-drops-146574 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.76 eng https://creativecommons.org/licenses/by/4.0/legalcode