Document Open Access Logo

Fast n-Fold Boolean Convolution via Additive Combinatorics

Authors Karl Bringmann, Vasileios Nakos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.41.pdf
  • Filesize: 0.7 MB
  • 17 pages

Document Identifiers

Author Details

Karl Bringmann
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Vasileios Nakos
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Funding

This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979).

Cite As Get BibTex

Karl Bringmann and Vasileios Nakos. Fast n-Fold Boolean Convolution via Additive Combinatorics. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.41

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • convolution
  • sumset computation
  • modular subset sum
  • output sensitive

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. Seth-based lower bounds for subset sum and bicriteria path. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41-57. SIAM, 2019. Google Scholar
  2. Amihood Amir, Ayelet Butman, and Ely Porat. On the relationship between histogram indexing and block-mass indexing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 372(2016):20130132, 2014. Google Scholar
  3. Amihood Amir, Oren Kapah, and Ely Porat. Deterministic length reduction: Fast convolution in sparse data and applications. In Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings, pages 183-194, 2007. Google Scholar
  4. Amihood Amir, Oren Kapah, Ely Porat, and Amir Rothschild. Polynomials: a new tool for length reduction in binary discrete convolutions. CoRR, 2014. Google Scholar
  5. Andrew Arnold and Daniel S Roche. Output-sensitive algorithms for sumset and sparse polynomial multiplication. In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, pages 29-36. ACM, 2015. Google Scholar
  6. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense Subset Sum may be the hardest. In Proc. of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 13:1-13:14, 2016. Google Scholar
  7. Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, and Hongxun Wu. Fast and simple modular subset sum. In Symposium on Simplicity in Algorithms (SOSA), pages 57-67. SIAM, 2021. Google Scholar
  8. Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, and Hongxun Wu. Fast modular subset sum using linear sketching. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 58-69. SIAM, 2019. Google Scholar
  9. Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas. Faster space-efficient algorithms for Subset Sum, k-Sum and related problems. In Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 198-209, 2017. Google Scholar
  10. Karl Bringmann. A near-linear pseudopolynomial time algorithm for Subset Sum. In Proc. of of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1073-1084, 2017. Google Scholar
  11. Karl Bringmann, Nick Fischer, and Vasileios Nakos. Sparse nonnegative convolution is equivalent to dense nonnegative convolution. In STOC 2021 (to appear). SIAM, 2021. Google Scholar
  12. Karl Bringmann and Vasileios Nakos. Top-k-convolution and the quest for near-linear output-sensitive subset sum. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 982-995, 2020. Google Scholar
  13. Jean Cardinal and John Iacono. Modular subset sum, dynamic strings, and zero-sum sets. In Symposium on Simplicity in Algorithms (SOSA), pages 45-56. SIAM, 2021. Google Scholar
  14. David E. Cardoze and Leonard J. Schulman. Pattern matching for spatial point sets. In 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 156-165, 1998. Google Scholar
  15. Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proc. of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 31-40, 2015. Google Scholar
  16. Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 592-601. ACM, 2002. Google Scholar
  17. Zvi Galil and Oded Margalit. An almost linear-time algorithm for the dense Subset-Sum problem. SIAM J. Comput., 20(6):1157-1189, 1991. Google Scholar
  18. Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray. Essentially optimal sparse polynomial multiplication. In Proceeding of the 45th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 202-209. ACM, 2020. Google Scholar
  19. Ce Jin and Hongxun Wu. A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, volume 69 of OASICS, pages 17:1-17:6, 2019. Google Scholar
  20. Konstantinos Koiliaris and Chao Xu. A faster pseudopolynomial time algorithm for Subset Sum. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1062-1072, 2017. Google Scholar
  21. Michael Monagan and Roman Pearce. Parallel sparse polynomial multiplication using heaps. In Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 263-270. ACM, 2009. Google Scholar
  22. Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. A subquadratic approximation scheme for partition. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 70-88, 2019. Google Scholar
  23. Shanmugavelayutham Muthukrishnan. New results and open problems related to non-standard stringology. In Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 937, pages 298-317. Springer, 1995. Google Scholar
  24. Vasileios Nakos. Nearly optimal sparse polynomial multiplication. IEEE Trans. Inf. Theory, 66(11):7231-7236, 2020. Google Scholar
  25. Daniel S Roche. Adaptive polynomial multiplication. Proc. Milestones in Computer Algebra (MICA’08), pages 65-72, 2008. Google Scholar
  26. Daniel S. Roche. What can (and can't) we do with sparse polynomials? In Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 25-30, 2018. Google Scholar
  27. Terence Tao and Van H. Vu. Additive Combinatorics, volume 105. Cambridge University Press, 2006. Google Scholar
  28. Joris Van Der Hoeven and Grégoire Lecerf. On the complexity of multivariate blockwise polynomial multiplication. In Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 211-218. ACM, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact