English

# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Fast n-fold Boolean Convolution via Additive Combinatorics

##### MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons251391

Nakos,  Vasileios
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### External Resource
No external resources are shared
##### Fulltext (restricted access)
There are currently no full texts shared for your IP range.
##### Fulltext (public)

arXiv:2105.03968.pdf
(Preprint), 291KB

##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Cite as: https://hdl.handle.net/21.11116/0000-0008-E25B-3
##### 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.