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 ?

  • 1
    $\begingroup$ $o(\text{polynomial})$ does not make much sense since both $n$ and $n^3$ are polynomials. It looks like you want $o(n\log n)$ multiplications. Can you edit the question to clarify? $\endgroup$ – John L. Mar 13 '19 at 1:30
  • $\begingroup$ The questions concerns computing a specific coefficient(of the resulting polynomial of multiplication) in sublinear time. One is allowed to pre-process the polynomial but the time for pre processing is less than the time it takes to multiply two polynomial (otherwise one can just compute the multiplication of the two polynomials and lookup specific coefficient in constant time) $\endgroup$ – E. Tzalic Mar 13 '19 at 18:26

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.

| cite | improve this answer | |
  • $\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 '19 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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