2007/06/11 by Andreas Björklund, Thore Husfeldt, Petteri Kaski +1 · 13 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithm #Circulant matrix #Circular convolution #Coding theory and cryptography #Combinatorics #Computer science #Convolution (computer science) #Convolution power #Convolution theorem #Discrete mathematics #Embedding #Fast Fourier transform #Fourier analysis #Fourier transform #Mathematical analysis #Mathematics #Overlap–add method #semigroups and automata theory
paper · doi:10.1145/1250790.1250801
openalex publication_date 2007/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-element set n, compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),,]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n2 2n) additions and multiplications, substanti y improving upon the straightforward O(3n) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2n M) time.