Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [convolution]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
1 answer

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 ...
Alexandr Pietriev's user avatar
2 votes
0 answers

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 ...
Alleo's user avatar
  • 121
17 votes
3 answers

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$ ...
Chao Xu's user avatar
  • 4,479
1 vote
0 answers

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 ...
chtenb's user avatar
  • 155
12 votes
1 answer

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(...
Thomas Ahle's user avatar
3 votes
1 answer

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?
Turbo's user avatar
  • 12.9k