# Item

ITEM ACTIONSEXPORT

Released

Paper

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

##### 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

Bringmann, K., & Nakos, V. (2021). Fast n-fold Boolean Convolution via Additive Combinatorics. Retrieved from https://arxiv.org/abs/2105.03968.

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.

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.