# Questions tagged [fft]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
16 votes
3 answers
2k 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$ ...
• 4,256
11 votes
1 answer
1k views

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(... • 778 7 votes 1 answer 195 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 ... 3 votes 1 answer 242 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? • 12.5k 2 votes 0 answers 127 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,080 2 votes 0 answers 87 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 ... • 121 1 vote 0 answers 33 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,080