computer science - 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.

• Next rt.representation theory - Resolution of singularities for nilpotent cone of the symplectic group
• Previous ag.algebraic geometry - How to find examples of non-trival kernel of maps between Brauer groups Br(R) -> Br(K)