Computing generalized convolutions faster than brute force

DOI10.1007/S00453-023-01176-2arXiv2209.01623OpenAlexW4387401092MaRDI QIDQ6185947FDOQ6185947

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

Publication date: 9 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In this paper, we consider a general notion of convolution. Let $D$ be a finite domain and let $D^n$ be the set of $n$-length vectors (tuples) of $D$. Let $f:DimesDoD$ be a function and let $oplu{s}_f$ be a coordinate-wise application of $f$. The $f$-Convolution of two functions $g,h:D^{n}o-M,ldots,M$ is ${\displaystyle }$(g otimes_f h)( extbf{v}) := sum_{substack{ extbf{v}_g, extbf{v}_h in D^n\ ext{s.t. } extbf{v}_g oplus_f extbf{v}_h}} g( extbf{v}_g) cdot h( extbf{v}_h)${\displaystyle }$ for every $extbfvin{D}^n$. 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 $widetildeO(|D{|}^{2n}mathrmpolylog(M))$ time. Our main result is an improvement over this naive algorithm. We show that $f$-Convolution can be computed exactly in $widetildeO((ccdot|D{|}^2{)}^{n}mathrmpolylog(M))$ for constant $c:=3/4$ when $D$ has even cardinality. Our main observation is that a emph{cyclic partition} of a function $f:DimesDoD$ 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^{n}o-M,ldots,M$ alongside with a vector $extbfvin{D}^n$ and the task of the $f$-Query problem is to compute integer $(gotime{s}_{f}h)(extbfv)$. This is a generalization of the well-known Orthogonal Vectors problem. We show that $f$-Query can be computed in $widetildeO(|D{|}^{fracomega2n}mathrmpolylog(M))$ time, where $omegain[2,2.372)$ is the exponent of currently fastest matrix multiplication algorithm.

Full work available at URL: https://arxiv.org/abs/2209.01623

zbMATH Keywords

generalized convolutionfast Fourier transformorthogonal vectorsfast subset convolution

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• An Algorithm for the Machine Calculation of Complex Fourier Series
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• Set partitioning via inclusion-exclusion
• Counting Paths and Packings in Halves
• Fourier meets M\"{o}bius: fast subset convolution
• Fast Zeta Transforms for Lattices with Few Irreducibles
• Exact and approximate bandwidth
• Fast generalized Fourier transforms
• Title not available (Why is that?)
• Explicit bounds for primes in arithmetic progressions
• More applications of the polynomial method to algorithm design
• Recent progress and applications in group FFTs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Clifford algebras meet tree decompositions
• Covering and packing in linear space
• On problems equivalent to \((\min,+)\)-convolution
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deterministic APSP, Orthogonal Vectors, and More
• On some fine-grained questions in algorithms and complexity
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
• A generic convolution algorithm for join operations on tree decompositions
• Faster minimization of tardy processing time on a single machine
• Title not available (Why is that?)
• Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
• Fast Algorithms for Join Operations on Tree Decompositions
• Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max

This page was built for publication: Computing generalized convolutions faster than brute force

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185947)