  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=+\infty) 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~(m^{5/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.
