hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We consider the problem of computing the Boolean convolution (with
wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of
computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq
\mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining
two subproblems, where the whole problem has a solution of size $k$ if for some
$i$ the first subproblem has a solution of size~$i$ and the second subproblem
has a solution of size $k-i$. Our problem formalizes a natural generalization,
namely combining solutions of $n$ subproblems subject to a modular constraint.
This simultaneously generalises Modular Subset Sum and Boolean Convolution
(Sumset Computation). Although nearly optimal algorithms are known for special
cases of this problem, not even tiny improvements are known for the general
case.
We almost resolve the computational complexity of this problem, shaving
essentially a factor of $n$ from the running time of previous algorithms.
Specifically, we present a \emph{deterministic} algorithm running in
\emph{almost} linear time with respect to the input plus output size $k$. We
also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear
expected time with respect to the input plus output size $k$. Previously, no
deterministic or randomized $o(nk)$ algorithm was known.
At the heart of our approach lies a careful usage of Kneser's theorem from
Additive Combinatorics, and a new deterministic almost linear output-sensitive
algorithm for non-negative sparse convolution. In total, our work builds a
solid toolbox that could be of independent interest.
