2018/07/12 by Kyriakos Axiotis, Axiotis, Kyriakos, Artūrs Bačkurs +3
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1807.04825
openalex publication_date 2018/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m=+∞) with ties to additive combinatorics and cryptography. Recently, in [Bringmann, SODA'17] and [Koiliaris and Xu, SODA'17], efficient algorithms have been developed for the non-modular case, running in near-linear pseudo-polynomial time. For the modular case, however, the best known algorithm by Koiliaris and Xu [Koiliaris and Xu, SODA'17] runs in time O~(m5/4). In this paper, we present an algorithm running in time O~(m), which matches a recent conditional lower bound of [Abboud et al.'17] based on the Strong Exponential Time Hypothesis. Interestingly, in contrast to most previous results on Subset Sum, our algorithm does not use the Fast Fourier Transform. Instead, it is able to simulate the "textbook" Dynamic Programming algorithm much faster, using ideas from linear sketching. This is one of the first applications of sketching-based techniques to obtain fast algorithms for combinatorial problems in an offline setting.