How do you quickly determine which coefficients are greater than zero when multiplying two univariate positive polynomials? Suppose that I have two polynomials with a degree of $n$, $A(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ and $B(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_0$ and the coefficients of these polynomials are zero or greater. Suppose I multiply $A(X)$ and $B(x)$, $C(x) = A(x)B(x)$. 
For the polynomial $C(x)$, how do I determine if the term $c_i$ is zero or greater? What is the fastest algorithm for determining whether for all terms $c_i$ if it is zero or nonzero?
 A: Since polynomial multiplication is essentially (non-cyclic) convolution, and for arbitrary polynomials $A(x),B(x)$, the fastest known convolution algorithms (based on the fast fourier transform) have complexity $O(d \log d)$ where $d=\max\{\deg A,\deg B\},$ without assumptions on the structure of the zero coefficients of $A$ and $B,$ there can't be a faster algorithm without any breakthroughs in algorithms computing convolutions. 
Edit: In the light of the comments, I now realize that it is correct one does not need to compute the full convolution. Modeling the nonzero coefficients of $A,B$ as subsets $S_A,S_B,$ of $\{1,\ldots,d\}$ the question can be related to computing properties of the sumset $S_A+S_B\subset \{1,2,\ldots,2d\}.$ 
It seems to me that in general this can be done in time $w_A w_B$ in the worst case where $w_A=\# S_A,$ is the weight (no. of nonzero coefficients) of the polynomial or the cardinality of $S_A,$ etc. So certainly, if $w_A w_B <d \log d,$ this would give an improvement. 
If the specific coefficient was $c_i,$ and we were only interested in whether $c_i$ was zero, then one would only need to consider the sets $S_A \cap \{0,1,2,\ldots,c_i\}$ and $S_b \cap \{0,1,2,\ldots c_i\}$ and by scanning forward in one and backward in the other set, while looking for two terms which sum to $c_i,$ one could actually determine if $c_i$ was nonzero or not in $O(c_i)$ time.
