1
$\begingroup$

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are integers. How do you determine what $p(x)$ is in the quickest way possible?

Motivation : Quickest way to determine a polynomial with positive integer coefficients

Question : How to prove the lower bound that you need at least $d$ many queries if the input polynomial has degree $d$?

$\endgroup$
0
$\begingroup$

$d$ queries at $a_1$, $\ldots$, $a_d$ cannot determine a polynomial $P$ of degree $d$ because all the polynomials $P + k(x-a_1)\cdots(x-a_d)$ give the same output for all those queries. So you need at least $d+1$. Clearly, $d+1$ are also sufficient.

$\endgroup$

Your Answer

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