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?
Question : How to prove the lower bound that you need at least $d$ many queries if the input polynomial has degree $d$?