# Is gaussian smoothing possible in less operations than O(N log N)

Gaussian filtering is popular in applications, for my question it can be written as (I've fixed the size of window):

$$y_i = \sum_{j = 1}^{n} x_j e^{(i - j)^2}, \qquad i = 1, 2, ..., n$$

One can implement this operation (computing y for given x) via FFT in $n \log(n)$ operations.

The question I am interested: is $n \log(n)$ really a limit? If yes, how can I prove this? If not - how do I write a faster implementation?

Example If I had laplacian kernel instead of gaussian, $$y_i = \sum_{j = 1}^{n} x_j e^{|i - j|}, \qquad i = 1, 2, ..., n,$$ I would be able to compute this in $O(n)$ operations.