Questions tagged [convolution]

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 ...
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$ ...
1
vote
0answers
153 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 ...
10
votes
1answer
512 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?