The [Convolution Theorem](http://mathworld.wolfram.com/ConvolutionTheorem.html%20%22Convolution%20Theorem%22) is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse transform on the result.


The same thing can be done for convolutions in the quotient ring Z/pZ via the analogous [Number Theoretic Transform](http://mathworld.wolfram.com/NumberTheoreticTransform.html).


Does this procedure generalize to other algebraic structures? Arbitrary rings? Semirings? Fast convolutions over the semiring (min,+) would be particularly useful.


I'm led to suspect this because both sorting and FFT can be computed using the same butterfly-like network with simple operations like "min", "max", "+", and "\*" at the nodes of the network, and sorting can be thought of as a kind of convolution.



does the "convolution theorem" apply to weaker algebraic structures?
In general, it is a major open question in discrete algorithms as to which algebraic structures admit fast convolution algorithms and which do not. (To be concrete, I define the *$(\oplus,\otimes)$ convolution* of two $n$-vectors $[x\_0,\ldots,x\_{n-1}]$ and $[y\_0,\ldots,y\_{n-1}]$, to be the vector $[z\_0,\ldots,z\_{n-1}]$ with $$z\_k = (x\_0 \otimes y\_k) \oplus (x\_1 \otimes y\_{k-1}) \oplus \cdots \oplus (x\_k \otimes y\_0).$$ Here, $\otimes$ and $\oplus$ are the multiplication and addition operations of some underlying semiring.) 


For any $\otimes$ and $\oplus$, the convolution can be computed trivially in $O(n^2)$ operations. As you note, when $\otimes = \times$, $\oplus = +$, and we work over the integers, this convolution can be done efficiently, in $O(n \log n)$ operations. 


But for more complex operations, we do not know efficient algorithms, and we do not know good lower bounds. The best algorithm for $(\min,+)$ convolution is $n^2/2^{\Omega (\sqrt{\log n})}$ operations, due to combining my recent APSP paper 



> 
> Ryan Williams: Faster all-pairs shortest paths via circuit complexity. STOC 2014: 664-673
> 
> 
> 


and



> 
> David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian: Necklaces, Convolutions, and X + Y. ESA 2006: 160-171
> 
> 
> 


A substantially subquadratic algorithm for $(\min,+)$ convolution would (to my knowledge) imply a subcubic algorithm all-pairs shortest paths in general graphs, a longstanding open problem. The above ESA06 reference also gives a $O(n^2 (\log \log n)^2/\log n)$ algorithm for a "(median,+) convolution".


The situation is subtle. It's not clear when convolution over a semiring is easy and when it's hard. For instance, the $(\min,\max)$ convolution *can* be computed in subquadratic time: I believe that $O(n^{3/2} \log n)$ operations suffice. This can be obtained from adapting the $(\min,\max)$ matrix multiplication algorithm in my work with Vassilevska and Yuster on all-pairs bottleneck paths. Basically you reduce the problem to computing $\sqrt{n}$ instances of a $(+,\times)$ ring convolution.


