Computing generalized convolutions faster than brute force
From MaRDI portal
Publication:6185947
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
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
