6 edited body edited Oct 16 '17 at 13:35 Complexity 53244 silver badges1919 bronze badges Black box of $$f(x)$$ means I can evaluate the polynomial $$f(x)$$ at any point. Input: aA black box of monic polynomial $$f(x) \in\mathbb{Z}^+[x]$$ of degree $$d$$. Output: theThe $$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? 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? 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? 5 Added tag, minor improvements edit approved Oct 14 '17 at 9:29 Rodrigo de Azevedo 75888 silver badges1616 bronze badges Black box of $$\mathcal{f(x)}$$$$f(x)$$ means I can evaluate the polynomial $$\mathcal{f(x)}$$$$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)$$. InputMy algorithm: : A black box of $$\mathcal{f(x)} \in\mathbb{Z^{+}(x)}$$, $$d$$ is the degree of the polynomiallet $$\mathcal{f(x)}$$(monic polynomial) Find : Coefficients of polynomial $$\mathcal{f(x)}$$$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$ My algorithm: let $$\mathcal{f(x)} = x^{d}+a_1x^{d-1}+\cdots+c$$, Evaluate polynomial $$\mathcal{f(x)}$$ overat $$d$$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equationequations to get the desired coefficients. ButHowever, 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? Black box of $$\mathcal{f(x)}$$ means I can evaluate the polynomial $$\mathcal{f(x)}$$ at any point. Input : A black box of $$\mathcal{f(x)} \in\mathbb{Z^{+}(x)}$$, $$d$$ is the degree of the polynomial $$\mathcal{f(x)}$$(monic polynomial) Find : Coefficients of polynomial $$\mathcal{f(x)}$$ My algorithm: let $$\mathcal{f(x)} = x^{d}+a_1x^{d-1}+\cdots+c$$, Evaluate polynomial $$\mathcal{f(x)}$$ over $$d$$ many points using black box and get a linear equations. Now I can solve the linear equation to get the desired coefficients. But in this case I need $$\mathcal{O(d)}$$ many queries to 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? 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? Tweeted twitter.com/StackCompSci/status/918854948942688258 occurred Oct 13 '17 at 15:04 4 added 4 characters in body edited Oct 13 '17 at 12:40 Complexity 53244 silver badges1919 bronze badges Black box of $$\mathcal{f(x)}$$ means I can evaluate the polynomial $$\mathcal{f(x)}$$ at any point. Input : A black box of $$\mathcal{f(x)} \in\mathbb{Z(x)}$$$$\mathcal{f(x)} \in\mathbb{Z^{+}(x)}$$, $$d$$ is the degree of the polynomial $$\mathcal{f(x)}$$(monic polynomial) Find : Coefficients of polynomial $$\mathcal{f(x)}$$ My algorithm: let $$\mathcal{f(x)} = x^{d}+a_1x^{d-1}+\cdots+c$$, Evaluate polynomial $$\mathcal{f(x)}$$ over $$d$$ many points using black box and get a linear equations. Now I can solve the linear equation to get the desired coefficients. But in this case I need $$\mathcal{O(d)}$$ many queries to 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? Black box of $$\mathcal{f(x)}$$ means I can evaluate the polynomial $$\mathcal{f(x)}$$ at any point. Input : A black box of $$\mathcal{f(x)} \in\mathbb{Z(x)}$$, $$d$$ is the degree of the polynomial $$\mathcal{f(x)}$$(monic polynomial) Find : Coefficients of polynomial $$\mathcal{f(x)}$$ My algorithm: let $$\mathcal{f(x)} = x^{d}+a_1x^{d-1}+\cdots+c$$, Evaluate polynomial $$\mathcal{f(x)}$$ over $$d$$ many points using black box and get a linear equations. Now I can solve the linear equation to get the desired coefficients. But in this case I need $$\mathcal{O(d)}$$ many queries to 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? Black box of $$\mathcal{f(x)}$$ means I can evaluate the polynomial $$\mathcal{f(x)}$$ at any point. Input : A black box of $$\mathcal{f(x)} \in\mathbb{Z^{+}(x)}$$, $$d$$ is the degree of the polynomial $$\mathcal{f(x)}$$(monic polynomial) Find : Coefficients of polynomial $$\mathcal{f(x)}$$ My algorithm: let $$\mathcal{f(x)} = x^{d}+a_1x^{d-1}+\cdots+c$$, Evaluate polynomial $$\mathcal{f(x)}$$ over $$d$$ many points using black box and get a linear equations. Now I can solve the linear equation to get the desired coefficients. But in this case I need $$\mathcal{O(d)}$$ many queries to 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? 3 added 1 character in body edited Oct 13 '17 at 12:37 Complexity 53244 silver badges1919 bronze badges 2 added 1 character in body edited Oct 13 '17 at 12:32 Complexity 53244 silver badges1919 bronze badges 1 asked Oct 13 '17 at 12:20 Complexity 53244 silver badges1919 bronze badges