Abstract
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 nearlinear 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 shifttree, is a simple variant of a segment tree. We provide both a hashingbased and a deterministic variant of the shifttrees.
We then apply our data structure to the Modular Subset Sum problem and obtain two algorithms. The first algorithm is MonteCarlo randomized and matches the 𝒪(m log m) runtime of the LasVegas 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.
BibTeX  Entry
@InProceedings{potepa:LIPIcs.ESA.2021.76,
author = {Pot\k{e}pa, Krzysztof},
title = {{Faster Deterministic Modular Subset Sum}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {76:176:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14657},
URN = {urn:nbn:de:0030drops146574},
doi = {10.4230/LIPIcs.ESA.2021.76},
annote = {Keywords: Modular Subset Sum, String Problem, Segment Tree, Data Structure}
}
Keywords: 

Modular Subset Sum, String Problem, Segment Tree, Data Structure 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 