Questions tagged [fft]
The fft tag has no usage guidance.
8
questions
1
vote
0
answers
52
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
7
votes
1
answer
200
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
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
2
votes
0
answers
131
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
92
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
17
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,367
12
votes
1
answer
1k
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(...
- 898
3
votes
1
answer
244
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.6k