# Questions tagged [fft]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
179 views

### Subquadratic 3SUM when one set is in [n^1.99]

Chan and Lewenstein (STOC 2015) said: 3SUM for three integer sets where only one set is assumed to be in $[n^{2−\delta}]$ can still be solved in subquadratic time (by doing several FFTs, without ...
32 views

### Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?

In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime. I've been toying with an idea for a ...
119 views

### What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
83 views

### 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 ...
1k views

### Finding witness in minkowski sum of integers

Let $A$ and $B$ be subsets of $\{0,\ldots,n\}$. We are interested in finding the Minkowski sum $A+B=\{a+b~|~a\in A,b\in B\}$. $\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ is a characteristic function of $X$ ...
We can do convolution in $O(n\log n)$ for plus/multiply polynomials with FFT. However, the approach doesn't seem very generalisable to rings in general. Has there been any progress over the naive \$O(...