Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 &lt; d &lt; p / 4$.

Although $f$ is unkonwn to us, there is an erroneous oracle $O$ satisfy the following property:
$\underset{(x,y)\in GF_p \times GF_p}{Pr}[O(x,y) = f(x,y)]\ge1 - \frac{1}{20d}$.

The question asks us to come up with a randomized algorithm which makes $O(d)$ queries to the oracle $O$ and returns the correct value of $f(0,0)$ with probability at least 0.9.

The following is my thinking process: the probability of $O(0, 0) = f(0, 0)$ is at least $1 - \frac{1}{20d}$ according to the condition before. If the probability is at least 0.9, then $d$ should be $d \ge \frac{1}{2}$. Then $p$ should be larger than $2$. We can assume the expression for $f$ is $a_db_dx^dy^d + a_db_{d-1}x^{d}y^{d-1} + a_{d-1}b_dx^{d-1}y^d + a_{d-1}b_{d-1}x^{d-1}y^{d-1} + ... + a_0b_0$. There are total $d^2$ number of items in the function. The randomized algorithm is that we could randomly select the value of $x$ and $y$ from $GF_p$, and at the following $d^2$ steps, we decide the parameters of the polynomials.

for i from 1 to d steps:
    for j from 1 to d stpes:
         randomly assign the values of other parameters except a_ib_j;
         solve the value of a_ib_j using the randomly assigned x, y and 
         the result queried from Oracle with x and y;


This is just my general idea. The problem is I do not know the degree $d$, so I cannot decide the exact number of steps $d^2$. And even if I know the degree $d$, how can I manage to decrease the time from $O(d^2)$ to $O(d)$?

Or maybe I am going in the wrong way. Can somebody help me with this?
Any help would be appreciated. Thanks in advance.
Some hints:

Could you solve the problem if the function was of the form $f : GF_p \to GF_p$, i.e., a univariate polynomial?  I suggest solving that special case first.  The below are some hints on how to do that:

If the error was zero, would you know what to do?  Could you devise a strategy that would always work in that situation?  How many queries would your strategy need?

Now suppose you applied your strategy, in the situation where there could be errors (but with the error probability bounded as you've described).  What's the probability that your strategy gives the wrong answer?  What's the probability that your strategy gives the right answer?

You might find it useful to use a union bound.

Can you think of any way to check whether a possible solution is correct?

Finally, once you can solve the univariate case, can you think of any way to repeat that procedure multiple times to handle the situation of a polynomial in two variables?