On (Near-)Optimal Algorithms for Sparse Convolution

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 non-zero coefficients in the input and output polynomials. The main result is a linear-time reduction of this problem to the multiplication of univariate polynomials of degree $O(t)$.

As a warm-up, Nick presented an over-simplified 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 non-zero 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 non-zero coefficient of $HASH_h(C)$ along with the corresponding coefficient of $HASH_h(C')$ yields the index of the corresponding non-zero coefficient of $C$, provided that this index is isolated by $h$.