License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.41
URN: urn:nbn:de:0030-drops-141108
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14110/
Go to the corresponding LIPIcs Volume Portal

Bringmann, Karl ; Nakos, Vasileios

Fast n-Fold Boolean Convolution via Additive Combinatorics

pdf-format:
LIPIcs-ICALP-2021-41.pdf (0.7 MB)

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 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 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 output-sensitive algorithm for non-negative 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 n-Fold Boolean Convolution via Additive Combinatorics}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14110},
  URN =		{urn:nbn:de:0030-drops-141108},
  doi =		{10.4230/LIPIcs.ICALP.2021.41},
  annote =	{Keywords: convolution, sumset computation, modular subset sum, output sensitive}
}

Keywords: convolution, sumset computation, modular subset sum, output sensitive
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI