# Find a polynomial in two or three queries

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

• Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.

• Output: The $d$ coefficients of polynomial $f(x)$.

My algorithm: let

$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$

Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.

However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?

• You keep changing the question. Perhaps you should first decide on your question and only then ask it. Otherwise it can be somewhat frustrating for the answerer. – Yuval Filmus Oct 13 '17 at 12:40
• What does $\mathbb{Z}^+$ means? – md5 Oct 13 '17 at 12:44
• set of positive integers – Complexity Oct 13 '17 at 12:45
• BTW for your algorithm, the coefficients can be computed in $O(n^2)$ instead of $O(n^3)$ with Lagrange's closed formula. – md5 Oct 13 '17 at 12:49
• Exact same question, worded differently: math.stackexchange.com/questions/446130/… – Nayuki Oct 14 '17 at 0:38

You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your choice and read off the coefficients from the base $x$ expansion.
Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.
• Sorry I did not get this part " I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero " – Complexity Oct 13 '17 at 13:09
• This is an adversary argument. Your algorithm asks the black box for the value of $f$ at $d-1$ places, and it always answers zero. I show that this is not enough for you to deduce the value of $f$. – Yuval Filmus Oct 13 '17 at 13:10