6 edited body
source | link

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
source | link

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
4 added 4 characters in body
source | link

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
source | link
2 added 1 character in body
source | link
1
source | link