In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of n-length vectors (tuples) of . Let be a function and let be a coordinate-wise application of f. The -CONVOLUTION of two functions is for every . This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain we can compute -CONVOLUTION via brute-force enumeration in time. Our main result is an improvement over this naive algorithm. We show that -CONVOLUTION can be computed exactly in for constant when has even cardinality. Our main observation is that a cyclic partition of a function can be used to speed up the computation of -CONVOLUTION, and we show that an appropriate cyclic partition exists for every f. Furthermore, we demonstrate that a single entry of the -CONVOLUTION can be computed more efficiently. In this variant, we are given two functions alongside with a vector and the task of the -QUERY problem is to compute integer . This is a generalization of the well-known Orthogonal Vectors problem. We show that -QUERY can be computed in time, where is the exponent of currently fastest matrix multiplication algorithm.
2024-01
2024-11-29