Computing sum of sparse polynomials squared in O(n log n) time? Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n&gt;m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient algorithm for computing the polynomial:

$$\sum_i p_i(x)^2$$

Since this polynomial has degree at most $2n$, both input and output size is $O(n)$. In the case $m=1$ we can compute the result using FFT in time $O(n \log n)$. Can this be done for any $m&lt;n$? If it makes any difference, I'm interested in the special case where coefficients are 0 and 1, and the computation should be done over the integers.

Update. I realized that a fast solution for the above would imply advances in fast matrix multiplication. In particular, if $p_k(x)=\sum_{i=1}^n a_{ik} x^i + \sum_{j=1}^n b_{kj} x^{nj}$ then we can read off $a_{ik} b_{kj}$ as the coefficient of $x^{i+nj}$ in $p_k(x)^2$. Thus, computing $p_k(x)^2$ corresponds to computing an outer product of two vectors, and computing the sum $\sum_k p_k(x)^2$ corresponds to computing a matrix product. If there is a solution using time $f(n,m)$ to computing $\sum_k p_k(x)^2$ then we can multiply two $n$-by-$n$ matrices in time $f(n^2,n)$, which means that $f(n,m)=O(n\log n)$ for $m\leq n$ would require a major breakthrough. But $f(n,m)=n^{\omega/2}$, where $\omega$ is the current exponent of matrix multiplication, might be possible. Ideas, anyone?
Squaring a polynomial with $x_i$ nonzero coefficients takes time $O(x_i^2)$ using ordinary term-by-term multiplication, so this should be preferred to the FFT for those polynomials where $x_i &lt; \sqrt{n \log n}$.  If $\sum_i x_i = n$, then the number of polynomials with $x_i$ greater than $\sqrt{n \log n}$ is $O(\sqrt{n / \log n})$, and these will take time $O(n^{3/2}({\log n})^{1/2})$ to square and combine (as will the remaining polynomials).  This is an improvement over the obvious $O(m n \log n)$ bound when $m$ is $\Theta(\sqrt{n / \log n})$.