Bringmann, Karl ;
Nakos, Vasileios
Fast nFold Boolean Convolution via Additive Combinatorics
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₁+A₂+…+A_n for A₁,…,A_n ⊆ ℤ_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 ki. 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 deterministic algorithm running in almost linear time with respect to the input plus output size k. We also present a Las Vegas algorithm running in 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 outputsensitive algorithm for nonnegative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs.ICALP.2021.41,
author = {Bringmann, Karl and Nakos, Vasileios},
title = {{Fast nFold Boolean Convolution via Additive Combinatorics}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {41:141:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14110},
URN = {urn:nbn:de:0030drops141108},
doi = {10.4230/LIPIcs.ICALP.2021.41},
annote = {Keywords: convolution, sumset computation, modular subset sum, output sensitive}
}
02.07.2021
Keywords: 

convolution, sumset computation, modular subset sum, output sensitive 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 