Computing generalized convolutions faster than brute force
type: Item
instance of: scholarly article
title: Computing generalized convolutions faster than brute force
arXiv ID: 2209.01623
author: Barış Can Esmer
author: Ariel Kulik
author: Dániel Marx
author: Philipp Schepper
author: Karol Węgrzycki
published in: Algorithmica
publication date: 2024-01-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/2209.01623
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7785284
zbMATH Keywords: generalized convolution
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: fast subset convolution
zbMATH Keywords: orthogonal vectors
MaRDI profile type: Publication
OpenAlex ID: W4387401092
cites work: More Applications of the Polynomial Method to Algorithm Design
cites work: Explicit bounds for primes in arithmetic progressions
cites work: Q3321411
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Counting Paths and Packings in Halves
cites work: Covering and packing in linear space
cites work: Fast Zeta Transforms for Lattices with Few Irreducibles
cites work: Set Partitioning via Inclusion-Exclusion
cites work: Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
cites work: Faster minimization of tardy processing time on a single machine
cites work: Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max
cites work: Deterministic APSP, Orthogonal Vectors, and More
cites work: Fast generalized Fourier transforms
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: On Problems Equivalent to (min,+)-Convolution
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Exact and approximate bandwidth
cites work: Q5874302
cites work: Q5111351
cites work: Q5875755
cites work: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
cites work: Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
cites work: Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
cites work: Q5290331
cites work: Fast Algorithms for Join Operations on Tree Decompositions
cites work: A generic convolution algorithm for join operations on tree decompositions
cites work: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
cites work: ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Clifford algebras meet tree decompositions
DOI: 10.1007/S00453-023-01176-2
description: scientific article; zbMATH DE number 7785284