Questions tagged [convolution]
The convolution tag has no usage guidance.
6
questions
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 ...
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
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
1
vote
0
answers
159
views
Algorithm for multiplying multivariate polynomials in a commutative ring
Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different ...
- 155
11
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(...
- 778
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