Polynomial multiplication coefficients I was wondering about the following interesting questions:
Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial.
What about finding a specific coefficient (or even deciding whether it is 0 or not) of some degree $k$ of the multiplication of an input? It is trivial to see that linear time in k is a must and sufficient as stated by D.W.
If one can preprocess the polynomial and query some specific coefficient is there an interesting $o(polynomial-multiplication)$ preprocessing and $o(k)$ per query ?
Yes, there are more efficient ways.  If you have two polynomials $p(x)=\sum p_i x^i$ and $q(x) = \sum q_i x^i$, then the coefficient of $x^k$ in $p(x) q(x)$ is given by

$$\sum_{i=0}^k p_i q_{k-i}.$$

This can be computed in $O(k)$ time, which is more efficient than multiplying the polynomials and extracting the coefficient of $x^k$.

With preprocessing, you can just multiply the polynomials during the preprocessing phase and store all of the coefficients.  Then looking up any desired coefficient can be done in $O(1)$ time.