0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That’s the trivial solution to the problems stated. What I am curios about is a strictly less than polynomial multiplication time for pre-processing and strictly less than linear time per query. $\endgroup$ – E. Tzalic Feb 9 at 18:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.