Find a polynomial in two or three queries - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:29:12Z https://cs.stackexchange.com/feeds/question/82409 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/82409 16 Find a polynomial in two or three queries Complexity https://cs.stackexchange.com/users/69130 2017-10-13T12:20:47Z 2017-10-16T13:35:17Z <p>Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.</p> <ul> <li><p><strong>Input</strong>: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.</p></li> <li><p><strong>Output:</strong> The $d$ coefficients of polynomial $f(x)$.</p></li> </ul> <p><strong>My algorithm:</strong> let </p> <p>$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$</p> <p>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.</p> <p>However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to <strong>minimize the number of queries</strong>. Is there any way to reduce the number of queries to just two or three?</p> https://cs.stackexchange.com/questions/82409/-/82411#82411 29 Answer by Yuval Filmus for Find a polynomial in two or three queries Yuval Filmus https://cs.stackexchange.com/users/683 2017-10-13T12:43:56Z 2017-10-13T12:43:56Z <p>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 &gt; M$ of your choice and read off the coefficients from the base $x$ expansion.</p> <p>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.</p>