Computing Generalized Convolutions Faster Than Brute Force

Authors Barış Can Esmer , Ariel Kulik, Dániel Marx , Philipp Schepper , Karol Węgrzycki



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.12.pdf
  • Filesize: 1.34 MB
  • 22 pages

Document Identifiers

Author Details

Barış Can Esmer
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Ariel Kulik
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Dániel Marx
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Philipp Schepper
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Karol Węgrzycki
  • Saarland University, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarbrücken, Germany

Acknowledgements

We would like to thank Karl Bringmann and Jesper Nederlof for useful discussions. Barış Can Esmer and Philipp Schepper are part of Saarbrücken Graduate School of Computer Science, Germany.

Cite AsGet BibTex

Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.12

Abstract

In this paper, we consider a general notion of convolution. Let D be a finite domain and let Dⁿ be the set of n-length vectors (tuples) of D. Let f : D × D → D be a function and let ⊕_f be a coordinate-wise application of f. The f-Convolution of two functions g,h : Dⁿ → {-M,…,M} is (g ⊛_f h)(v) := ∑_{v_g,v_h ∈ D^n s.t. v = v_g ⊕_f v_h} g(v_g) ⋅ h(v_h) for every 𝐯 ∈ Dⁿ. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain D we can compute f-Convolution via brute-force enumeration in 𝒪̃(|D|^{2n} ⋅ polylog(M)) time. Our main result is an improvement over this naive algorithm. We show that f-Convolution can be computed exactly in 𝒪̃((c ⋅ |D|²)ⁿ ⋅ polylog(M)) for constant c := 5/6 when D has even cardinality. Our main observation is that a cyclic partition of a function f : D × D → D can be used to speed up the computation of f-Convolution, and we show that an appropriate cyclic partition exists for every f. Furthermore, we demonstrate that a single entry of the f-Convolution can be computed more efficiently. In this variant, we are given two functions g,h : Dⁿ → {-M,…,M} alongside with a vector 𝐯 ∈ Dⁿ and the task of the f-Query problem is to compute integer (g ⊛_f h)(𝐯). This is a generalization of the well-known Orthogonal Vectors problem. We show that f-Query can be computed in 𝒪̃(|D|^{(ω/2)n} ⋅ polylog(M)) time, where ω ∈ [2,2.373) is the exponent of currently fastest matrix multiplication algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Algorithm design techniques
Keywords
  • Generalized Convolution
  • Fast Fourier Transform
  • Fast Subset Convolution

Metrics

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

References

  1. Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More Applications of the Polynomial Method to Algorithm Design. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 218-230. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.17.
  2. Josh Alman and Virginia Vassilevska Williams. A Refined Laser Method and Faster Matrix Multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  3. Michael A. Bennett, Greg Martin, Kevin O'Bryant, and Andrew Rechnitzer. Explicit bounds for primes in arithmetic progressions. Illinois J. Math., 62(1-4):427-532, 2018. URL: https://doi.org/10.1215/ijm/1552442669.
  4. Thomas Beth. Verfahren der schnellen Fourier-Transformation: die allgemeine diskrete Fourier-Transformation-ihre algebraische Beschreibung, Komplexität und Implementierung, volume 61. Teubner, 1984. Google Scholar
  5. Andreas Björklund and Thore Husfeldt. The Parity of Directed Hamiltonian Cycles. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 727-735. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.83.
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier Meets Möbius: Fast Subset Convolution. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74. ACM, 2007. URL: https://doi.org/10.1145/1250790.1250801.
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Paths and Packings in Halves. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 578-586. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_52.
  8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Covering and packing in linear space. Inf. Process. Lett., 111(21-22):1033-1036, 2011. URL: https://doi.org/10.1016/j.ipl.2011.08.002.
  9. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen. Fast Zeta Transforms for Lattices with Few Irreducibles. ACM Trans. Algorithms, 12(1):4:1-4:19, 2016. URL: https://doi.org/10.1145/2629429.
  10. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. SIAM J. Comput., 39(2):546-563, 2009. URL: https://doi.org/10.1137/070683933.
  11. Cornelius Brand. Discriminantal subset convolution: Refining exterior-algebraic methods for parameterized algorithms. Journal of Computer and System Sciences, 129:62-71, 2022. URL: https://doi.org/10.1016/j.jcss.2022.05.004.
  12. Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, and Philip Wellnitz. Faster Minimization of Tardy Processing Time on a Single Machine. Algorithmica, 84(5):1341-1356, 2022. URL: https://doi.org/10.1007/s00453-022-00928-w.
  13. Karl Bringmann, Marvin Künnemann, and Karol Węgrzycki. Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 943-954, 2019. Google Scholar
  14. Timothy M. Chan and Qizheng He. Reducing 3SUM to Convolution-3SUM. In Martin Farach-Colton and Inge Li Gørtz, editors, 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020, pages 1-7. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976014.1.
  15. Timothy M. Chan and R. Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. ACM Trans. Algorithms, 17(1):2:1-2:14, 2021. URL: https://doi.org/10.1145/3402926.
  16. Gary Chartrand, Albert D Polimeni, and M James Stewart. The existence of 1-factors in line graphs, squares, and total graphs. In Indagationes Mathematicae (Proceedings), volume 76, pages 228-232. Elsevier, 1973. Google Scholar
  17. Michael Clausen. Fast generalized Fourier transforms. Theoretical Computer Science, 67(1):55-63, 1989. Google Scholar
  18. James W Cooley and John W Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, 19(90):297-301, 1965. Google Scholar
  19. Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michal Włodarczyk. On Problems Equivalent to (min, +)-Convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. URL: https://doi.org/10.1145/3293465.
  20. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. ACM Trans. Algorithms, 18(2):17:1-17:31, 2022. URL: https://doi.org/10.1145/3506707.
  21. Marek Cygan and Marcin Pilipczuk. Exact and approximate bandwidth. Theor. Comput. Sci., 411(40-42):3701-3713, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.018.
  22. Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force, 2022. URL: https://doi.org/10.48550/ARXIV.2209.01623.
  23. Philip Hall. A contribution to the theory of groups of prime-power order. Proceedings of the London Mathematical Society, 2(1):29-95, 1934. Google Scholar
  24. Falko Hegerfeld and Stefan Kratsch. Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 29:1-29:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.29.
  25. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.21.
  26. Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 53:1-53:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.53.
  27. Jesper Nederlof. personal communication, 2022. Google Scholar
  28. Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, and Karol Węgrzycki. A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 1682-1701. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.102.
  29. Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, and Karol Węgrzycki. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space. In Isolde Adler and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, volume 12301 of Lecture Notes in Computer Science, pages 27-39. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-60440-0_3.
  30. Jesper Nederlof and Karol Węgrzycki. Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1670-1683. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451024.
  31. Daniel N Rockmore. Recent progress and applications in group FFTs. In Computational noncommutative algebra and applications, pages 227-254. Springer, 2004. Google Scholar
  32. Chris Umans. Fast Generalized DFTs for all Finite Groups. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 793-805. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00052.
  33. Johan M. M. van Rooij. Fast Algorithms for Join Operations on Tree Decompositions. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 262-297. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-42071-0_18.
  34. Johan M. M. van Rooij. A Generic Convolution Algorithm for Join Operations on Tree Decompositions. In Rahul Santhanam and Daniil Musatov, editors, Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 - July 2, 2021, Proceedings, volume 12730 of Lecture Notes in Computer Science, pages 435-459. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79416-3_27.
  35. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
  36. Virginia Vassilevska-Williams. On Some Fine-Grained Questions in Algorithms and Complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447-34, 2018. Google Scholar
  37. Louis Weisner. Abstract theory of inversion of finite series. Transactions of the American Mathematical Society, 38(3):474-484, 1935. Google Scholar
  38. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  39. Michał Włodarczyk. Clifford Algebras Meet Tree Decompositions. Algorithmica, 81(2):497-518, 2019. URL: https://doi.org/10.1007/s00453-018-0489-3.
  40. Frank Yates. The design and analysis of factorial experiments. Technical Communication No. 35., 1937. Google Scholar
  41. Or Zamir. Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 113:1-113:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.113.
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