Computing generalized convolutions faster than brute force

DOI10.1007/s00453-023-01176-2arXiv2209.01623OpenAlexW4387401092MaRDI QIDQ6185947

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

Publication date: 9 January 2024

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

fast Fourier transformorthogonal vectorsgeneralized convolutionfast subset convolution

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit bounds for primes in arithmetic progressions
• Exact and approximate bandwidth
• Fast generalized Fourier transforms
• Clifford algebras meet tree decompositions
• Covering and packing in linear space
• 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
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Counting Paths and Packings in Halves
• On Problems Equivalent to (min,+)-Convolution
• Fast Zeta Transforms for Lattices with Few Irreducibles
• Deterministic APSP, Orthogonal Vectors, and More
• Fast Algorithms for Join Operations on Tree Decompositions
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max
• An Algorithm for the Machine Calculation of Complex Fourier Series
• More Applications of the Polynomial Method to Algorithm Design
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

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