{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:14Z","timestamp":1740109334888,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["725978","725978","725978","725978","850979"],"award-info":[{"award-number":["725978","725978","725978","725978","850979"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Helmholtz-Zentrum f\u00fcr Informationssicherheit \u2013 CISPA gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>In this paper, we consider a general notion of convolution. Let $$D$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a finite domain and let $$D^n$$<\/jats:tex-math>\n \n D<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be the set of n<\/jats:italic>-length vectors (tuples) of $$D$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Let $$f :D\\times D\\rightarrow D$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n D<\/mml:mi>\n \u00d7<\/mml:mo>\n D<\/mml:mi>\n \u2192<\/mml:mo>\n D<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a function and let $$\\oplus _f$$<\/jats:tex-math>\n \n \u2295<\/mml:mo>\n f<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a coordinate-wise application of f<\/jats:italic>. The $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Convolution<\/jats:sc> of two functions $$g,h :D^n \\rightarrow \\{-M,\\ldots ,M\\}$$<\/jats:tex-math>\n \n g<\/mml:mi>\n ,<\/mml:mo>\n h<\/mml:mi>\n :<\/mml:mo>\n \n D<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n \u2192<\/mml:mo>\n \n {<\/mml:mo>\n -<\/mml:mo>\n M<\/mml:mi>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n M<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is $$\\begin{aligned} (g \\mathbin {\\circledast _{f}}h)(\\textbf{v}) {:}{=}\\sum _{\\begin{array}{c} \\textbf{v}_g,\\textbf{v}_h \\in D^n\\\\ \\text {s.t. } \\textbf{v}= \\textbf{v}_g \\oplus _f \\textbf{v}_h \\end{array}} g(\\textbf{v}_g) \\cdot h(\\textbf{v}_h) \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n (<\/mml:mo>\n g<\/mml:mi>\n \n \u229b<\/mml:mo>\n f<\/mml:mi>\n <\/mml:msub>\n h<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n :<\/mml:mo>\n =<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n \n \n \n \n \n v<\/mml:mi>\n g<\/mml:mi>\n <\/mml:msub>\n ,<\/mml:mo>\n \n v<\/mml:mi>\n h<\/mml:mi>\n <\/mml:msub>\n \u2208<\/mml:mo>\n \n D<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n s.t.<\/mml:mtext>\n \n v<\/mml:mi>\n =<\/mml:mo>\n \n v<\/mml:mi>\n g<\/mml:mi>\n <\/mml:msub>\n \n \u2295<\/mml:mo>\n f<\/mml:mi>\n <\/mml:msub>\n \n v<\/mml:mi>\n h<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:munder>\n g<\/mml:mi>\n \n (<\/mml:mo>\n \n v<\/mml:mi>\n g<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n h<\/mml:mi>\n \n (<\/mml:mo>\n \n v<\/mml:mi>\n h<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula>for every $$\\textbf{v}\\in D^n$$<\/jats:tex-math>\n \n v<\/mml:mi>\n \u2208<\/mml:mo>\n \n D<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f<\/jats:italic> and domain $$D$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> we can compute $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Convolution<\/jats:sc> via brute-force enumeration in $$\\widetilde{{\\mathcal {O}}}(|D|^{2n} \\cdot \\textrm{polylog}(M))$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n \n (<\/mml:mo>\n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u00b7<\/mml:mo>\n polylog<\/mml:mtext>\n \n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. Our main result is an improvement over this naive algorithm. We show that $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Convolution<\/jats:sc> can be computed exactly in $$\\widetilde{{\\mathcal {O}}}( (c \\cdot |D|^2)^{n} \\cdot \\textrm{polylog}(M))$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n (<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n \n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \n )<\/mml:mo>\n n<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n polylog<\/mml:mtext>\n \n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for constant $$c {:}{=}3\/4$$<\/jats:tex-math>\n \n c<\/mml:mi>\n :<\/mml:mo>\n =<\/mml:mo>\n 3<\/mml:mn>\n \/<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when $$D$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has even cardinality. Our main observation is that a cyclic partition<\/jats:italic> of a function $$f :D\\times D\\rightarrow D$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n D<\/mml:mi>\n \u00d7<\/mml:mo>\n D<\/mml:mi>\n \u2192<\/mml:mo>\n D<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be used to speed up the computation of $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Convolution<\/jats:sc>, and we show that an appropriate cyclic partition exists for every f<\/jats:italic>. Furthermore, we demonstrate that a single entry of the $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Convolution<\/jats:sc> can be computed more efficiently. In this variant, we are given two functions $$g,h :D^n \\rightarrow \\{-M,\\ldots ,M\\}$$<\/jats:tex-math>\n \n g<\/mml:mi>\n ,<\/mml:mo>\n h<\/mml:mi>\n :<\/mml:mo>\n \n D<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n \u2192<\/mml:mo>\n \n {<\/mml:mo>\n -<\/mml:mo>\n M<\/mml:mi>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n M<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> alongside with a vector $$\\textbf{v}\\in D^n$$<\/jats:tex-math>\n \n v<\/mml:mi>\n \u2208<\/mml:mo>\n \n D<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the task of the $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Query<\/jats:sc> problem is to compute integer $$(g \\mathbin {\\circledast _{f}}h)(\\textbf{v})$$<\/jats:tex-math>\n \n (<\/mml:mo>\n g<\/mml:mi>\n \n \u229b<\/mml:mo>\n f<\/mml:mi>\n <\/mml:msub>\n h<\/mml:mi>\n )<\/mml:mo>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This is a generalization of the well-known Orthogonal Vectors problem. We show that $$f$$<\/jats:tex-math>\n f<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Query<\/jats:sc> can be computed in $$\\widetilde{{\\mathcal {O}}}(|D|^{\\frac{\\omega }{2} n} \\cdot \\textrm{polylog}(M))$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n \n (<\/mml:mo>\n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \n \n \u03c9<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:mfrac>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u00b7<\/mml:mo>\n polylog<\/mml:mtext>\n \n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where $$\\omega \\in [2,2.372)$$<\/jats:tex-math>\n \n \u03c9<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 2.372<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the exponent of currently fastest matrix multiplication algorithm.<\/jats:p>","DOI":"10.1007\/s00453-023-01176-2","type":"journal-article","created":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T12:01:42Z","timestamp":1696593702000},"page":"334-366","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Generalized Convolutions Faster Than Brute Force"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5694-1465","authenticated-orcid":false,"given":"Bar\u0131\u015f Can","family":"Esmer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Kulik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5810-7949","authenticated-orcid":false,"given":"Philipp","family":"Schepper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9746-5733","authenticated-orcid":false,"given":"Karol","family":"W\u0119grzycki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,6]]},"reference":[{"key":"1176_CR1","unstructured":"Abboud, A., Williams, R.R., Yu, H.: More applications of the polynomial method to algorithm design. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 218\u2013230. SIAM (2015)"},{"key":"1176_CR2","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Marx D (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021. SIAM, pp. 522\u2013539 (2021)","DOI":"10.1137\/1.9781611976465.32"},{"issue":"1\u20134","key":"1176_CR3","first-page":"427","volume":"62","author":"MA Bennett","year":"2018","unstructured":"Bennett, M.A., Martin, G., O\u2019Bryant, K., Rechnitzer, A.: Explicit bounds for primes in arithmetic progressions. Ill. J. Math. 62(1\u20134), 427\u2013532 (2018)","journal-title":"Ill. J. Math."},{"key":"1176_CR4","unstructured":"Beth, T.: Verfahren der schnellen Fourier-Transformation: die allgemeine diskrete Fourier-Transformation\u2013ihre algebraische Beschreibung, Komplexit\u00e4t und Implementierung, vol.\u00a061. Teubner (1984)"},{"key":"1176_CR5","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: The parity of directed Hamiltonian cycles. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October, 2013, Berkeley, CA, USA, pp. 727\u2013735. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.83"},{"key":"1176_CR6","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11\u201313, 2007, pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"1176_CR7","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat A, Sanders P (eds.) Algorithms\u2014ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7\u20139, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pp. 578\u2013586. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_52"},{"issue":"21\u201322","key":"1176_CR8","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1016\/j.ipl.2011.08.002","volume":"111","author":"A Bj\u00f6rklund","year":"2011","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Covering and packing in linear space. Inf. Process. Lett. 111(21\u201322), 1033\u20131036 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1176_CR9","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2629429","volume":"12","author":"A Bj\u00f6rklund","year":"2016","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M., Nederlof, J., Parviainen, P.: Fast zeta transforms for lattices with few irreducibles. ACM Trans. Algorithms 12(1), 4:1-4:19 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1176_CR10","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"1176_CR11","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.jcss.2022.05.004","volume":"129","author":"C Brand","year":"2022","unstructured":"Brand, C.: Discriminantal subset convolution: Refining exterior-algebraic methods for parameterized algorithms. J. Comput. Syst. Sci. 129, 62\u201371 (2022)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1176_CR12","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1007\/s00453-022-00928-w","volume":"84","author":"K Bringmann","year":"2022","unstructured":"Bringmann, K., Fischer, N., Hermelin, D., Shabtay, D., Wellnitz, P.: Faster minimization of tardy processing time on a single machine. Algorithmica 84(5), 1341\u20131356 (2022)","journal-title":"Algorithmica"},{"key":"1176_CR13","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M., W\u0119grzycki, K.: 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, pp. 943\u2013954 (2019)","DOI":"10.1145\/3313276.3316373"},{"key":"1176_CR14","doi-asserted-by":"crossref","unstructured":"Chan, T.M., He, Q.: Reducing 3SUM to convolution-3SUM. In: Farach-Colton, M., G\u00f8rtz, I.L. (eds.) 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6\u20137, 2020, pp. 1\u20137. SIAM (2020)","DOI":"10.1137\/1.9781611976014.1"},{"issue":"1","key":"1176_CR15","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/3402926","volume":"17","author":"TM Chan","year":"2021","unstructured":"Chan, T.M., Williams, R.R.: Deterministic APSP, Orthogonal Vectors, and more: quickly derandomizing Razborov\u2013Smolensky. ACM Trans. Algorithms 17(1), 2:1-2:14 (2021)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1176_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0304-3975(89)90021-2","volume":"67","author":"M Clausen","year":"1989","unstructured":"Clausen, M.: Fast generalized Fourier transforms. Theor. Comput. Sci. 67(1), 55\u201363 (1989)","journal-title":"Theor. Comput. Sci."},{"issue":"90","key":"1176_CR17","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297\u2013301 (1965)","journal-title":"Math. Comput."},{"issue":"1","key":"1176_CR18","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3293465","volume":"15","author":"M Cygan","year":"2019","unstructured":"Cygan, M., Mucha, M., W\u0119grzycki, K., W\u0142odarczyk, M.: On problems equivalent to $$(\\min , +)$$-convolution. ACM Trans. Algorithms 15(1), 14:1-14:25 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1176_CR19","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3506707","volume":"18","author":"M Cygan","year":"2022","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms 18(2), 17:1-17:31 (2022)","journal-title":"ACM Trans. Algorithms"},{"issue":"40\u201342","key":"1176_CR20","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40\u201342), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"1176_CR21","doi-asserted-by":"crossref","unstructured":"Duan, R., Wu, H., Zhou, R.: Faster Matrix Multiplication via Asymmetric Hashing. CoRR arXiv:2210.10173 (2022)","DOI":"10.1109\/FOCS57990.2023.00130"},{"issue":"1","key":"1176_CR22","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1112\/plms\/s2-36.1.29","volume":"2","author":"P Hall","year":"1934","unstructured":"Hall, P.: A contribution to the theory of groups of prime-power order. Proc. Lond. Math. Soc. 2(1), 29\u201395 (1934)","journal-title":"Proc. Lond. Math. Soc."},{"key":"1176_CR23","unstructured":"Hegerfeld, F., Kratsch, S.: Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10\u201313, 2020, Montpellier, France, volume 154 of LIPIcs, pp. 29:1\u201329:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1176_CR24","doi-asserted-by":"crossref","unstructured":"Hegerfeld, F., Kratsch, S.: Tight algorithms for connectivity problems parameterized by clique-width. In: Proceedings of ESA (2023) (to appear)","DOI":"10.1007\/978-3-031-43380-1_28"},{"key":"1176_CR25","unstructured":"K\u00fcnnemann, M., Paturi, R., Schneider, S.: On the fine-grained complexity of one-dimensional dynamic programming. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10\u201314, 2017, Warsaw, Poland, volume\u00a080 of LIPIcs, pp. 21:1\u201321:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"1176_CR26","unstructured":"Lincoln, A., Polak, A., Williams, V.V.: Monochromatic triangles, intermediate matrix products, and convolutions. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12\u201314, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pp. 53:1\u201353:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1176_CR27","unstructured":"Nederlof, J.: Personal communication (2022)"},{"key":"1176_CR28","doi-asserted-by":"crossref","unstructured":"Nederlof, J., Pawlewicz, J., Swennenhuis, C.M.F., W\u0119grzycki, K.: A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 1682\u20131701. SIAM (2021)","DOI":"10.1137\/1.9781611976465.102"},{"key":"1176_CR29","doi-asserted-by":"crossref","unstructured":"Nederlof, J., Pilipczuk, M., Swennenhuis, C.M.F., W\u0119grzycki, K.: Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space. In: Adler, I., M\u00fcller, H. (eds) Graph-Theoretic Concepts in Computer Science\u201446th International Workshop, WG 2020, Leeds, UK, June 24\u201326, 2020, Revised Selected Papers, volume 12301 of Lecture Notes in Computer Science, pp. 27\u201339. Springer (2020)","DOI":"10.1007\/978-3-030-60440-0_3"},{"key":"1176_CR30","doi-asserted-by":"crossref","unstructured":"Nederlof, J., W\u0119grzycki, K.: Improving Schroeppel and Shamir\u2019s algorithm for subset sum via Orthogonal Vectors. In: Khuller, S., Williams, V.V. (eds.) STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, pp. 1670\u20131683. ACM (2021)","DOI":"10.1145\/3406325.3451024"},{"key":"1176_CR31","first-page":"227","volume-title":"Computational noncommutative algebra and applications","author":"DN Rockmore","year":"2004","unstructured":"Rockmore, D.N.: Recent progress and applications in group FFTs. In: Byrnes, J. (ed.) Computational noncommutative algebra and applications, pp. 227\u2013254. Springer, Berlin (2004)"},{"key":"1176_CR32","doi-asserted-by":"crossref","unstructured":"Umans, C.: Fast generalized DFTs for all finite groups. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9\u201312, 2019, pp. 793\u2013805. IEEE Computer Society (2019)","DOI":"10.1109\/FOCS.2019.00052"},{"key":"1176_CR33","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M.: Fast algorithms for join operations on tree decompositions. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms\u2014Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pp. 262\u2013297. Springer (2020)","DOI":"10.1007\/978-3-030-42071-0_18"},{"key":"1176_CR34","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M.: A generic convolution algorithm for join operations on tree decompositions. In: Santhanam, R., Musatov, D. (eds.) Computer Science\u2014Theory and Applications\u201416th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28\u2013July 2, 2021, Proceedings, volume 12730 of Lecture Notes in Computer Science, pp. 435\u2013459. Springer (2021)","DOI":"10.1007\/978-3-030-79416-3_27"},{"key":"1176_CR35","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) Algorithms\u2014ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7\u20139, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pp. 566\u2013577. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"1176_CR36","doi-asserted-by":"crossref","unstructured":"Vassilevska-Williams, V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians (ICM 2018), pp. 3447\u201334 (2018)","DOI":"10.1142\/9789813272880_0188"},{"issue":"3","key":"1176_CR37","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1090\/S0002-9947-1935-1501822-0","volume":"38","author":"L Weisner","year":"1935","unstructured":"Weisner, L.: Abstract theory of inversion of finite series. Trans. Am. Math. Soc. 38(3), 474\u2013484 (1935)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2\u20133","key":"1176_CR38","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1176_CR39","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/s00453-018-0489-3","volume":"81","author":"M W\u0142odarczyk","year":"2019","unstructured":"W\u0142odarczyk, M.: Clifford algebras meet tree decompositions. Algorithmica 81(2), 497\u2013518 (2019)","journal-title":"Algorithmica"},{"key":"1176_CR40","unstructured":"Yates, F.: The design and analysis of factorial experiments. Imperial Bureau of Soil Science. Technical Communication (1937)"},{"key":"1176_CR41","unstructured":"Zamir, O.: Breaking the $${2^{n}}$$ barrier for 5-coloring and 6-coloring. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pp. 113:1\u2013113:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01176-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01176-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01176-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T17:04:39Z","timestamp":1704301479000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01176-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,6]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1176"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01176-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,10,6]]},"assertion":[{"value":"13 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}