Questions tagged [fft]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7
votes
1answer
177 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 ...
1
vote
0answers
31 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 ...
2
votes
0answers
116 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 ...
2
votes
0answers
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 ...
16
votes
3answers
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$ ...
10
votes
1answer
513 views

Complexity of convolution in the max/plus ring

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(...
3
votes
1answer
213 views

Convolution without FFT

What is the best upper and lower bound known for convolution without FFT? Is FFT proven to be essential for time complexity reduction? Is cancellation essential as well?