Let $K=\mathbb{Z}$ or $K=\mathbb{Q}$. Let $f \in K[x]$ and $x_i,y_i \in K$.

Let $x_i$ be $n$ elements of $K$ randomly chosen, where $n > d = 2 \deg(f)$.

Given $\{a_i=f(x_i)\}$ ($x_i$ are unknown) and $d$, what are the best algorithms to find $f$ or another polynomial $g$, satisfying $a_i=g(y_i)$ for known $y_i$, possibly $x_i=y_i$?

One approach is to treat the coefficients of $f$ and $x_i$ as unknowns and try to find $K$ points on the variety, but this appears hard to me.

If $x_i$ are known, the problem is easy.

Let $K=\mathbb{Z}$ or $K=\mathbb{Q}$. Let $f \in K[x],\deg(f)>1$ and $x_i,y_i \in K$.

Let $x_i$ be $n$ elements of $K$ randomly chosen, where $n > d = 2 \deg(f)$.

Given $\{a_i=f(x_i)\}$ ($x_i$ are unknown) and $d$, what are the best algorithms to find $f$ or another polynomial $g$, satisfying $a_i=g(y_i)$ for known $y_i$, possibly $x_i=y_i$?

One approach is to treat the coefficients of $f$ and $x_i$ as unknowns and try to find $K$ points on the variety, but this appears hard to me.

If $x_i$ are known, the problem is easy.