As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [fft]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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
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
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
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
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
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