On (Near)Optimal Algorithms for Sparse Convolution
by Nick Fischer
Oded's comments
The talk actually focused on multiplying sparse polynomials,
or rather on an optimal reduction of this problem to the
problem of multiplying general (univariate) polynomials.
Specifically, the input is a pair of univariate polynomials
of degree $n$, and $t$ is a bound on the number of nonzero
coefficients in the input and output polynomials.
The main result is a lineartime reduction of this problem
to the multiplication of univariate polynomials of degree $O(t)$.
As a warmup, Nick presented an oversimplified randomized reduction,
which is worse by a polylogarithmic factor.
The basic idea is using an adequate hashing of high degree polynomials
to polynomials of degree that relates to the sparsity parameter, $t$.
Specifically, the polynomial $P(x)=\sum_{i=0}^n p_i x^i$
is mapped to the polynomial $HASH_h(P)=\sum_{i=I}^n p_i x^{h(i)}$,
where $h(i)=i mod m$ and $m$ is a random prime of size $O(t\log n)$.
The key observations are:

$$(\sum_{i} a_i x^{h(i)})\cdot(\sum_{j} b_j x^{h(j)})
= \sum_{i,j} a_i b_j x^{h(i)+h(j)})
= \sum_{i,j} a_i b_j x^{i+j mod m})$$

Letting $K$ denote the indices of the nonzero coefficients
in the product of the input polynomials,
we say that $k\in K$ is isolated by $h$ if $h(k')\neq h(k)$
for every $k'\in K\setminus\{k\}$.
Each element of $K$ is isolated with high probability,
over the choice of $h$, but these events are not indepdendent.

Denoting the said product by $C=\sum_{k\in K} c_k x^k$
and assuming that $k\in K$ is isolated under $h$,
we note that the coefficient of $x^{h(k)}$ in $HASH_h(C)$ equals $c_k$.
Likewise, the coefficient of $x^{h(k)1}$ in $HASH_h(C')$ equals $k c_k$,
where $C'$ is the derivative of $C=AB$ obtained by $A'B+AB'$.
Hence, a nonzero coefficient of $HASH_h(C)$
along with the corresponding coefficient of $HASH_h(C')$
yields the index of the corresponding nonzero coefficient of $C$,
provided that this index is isolated by $h$.
(The foregoing does not really work as is,
but is rather meant to provide some feeling of the ideas involved.)
Back to
list of Oded's choices.