Testing low degree bivariate polynomials

Question

Let $d,q \in \mathbb{N}$, and let $f:\mathrm{GF}(q) \to \mathrm{GF}(q)$ be a univariate polynomial. In this case, it is possible to test whether $f$ is of degree at most $d$ (or whether $f$ is at least $\epsilon$ from it) using the algorithm of (RS96). The testing algorithm works by simply trying to interpolate the function $f$ on $\Theta(1/\epsilon)$ collections of $d + 2$ uniformly selected points, and checking whether the resulting functions are all polynomial of degree at most $d$.

Is there an extension of this result that allows to test whether a bivariate polynomial $g:\mathrm{GF}(q)^2 \to \mathrm{GF}(q)$ is of degree at most $d$ in the first variable, using $O(\epsilon^{-1} \cdot d)$ queries?

Answer 1

If you only care about the first variable, then I believe the following simple test should work: pick a random value $\beta \in \rm{GF}(q)$ and check that $f(\cdot, \beta)$ is a univariate polynomial of degree at most $d$ - say, by choosing few collections of $d+2$ points of the form $(\cdot,\beta)$ and interpolating them.

The analysis of this test should be trivial: If the function is far from being of degree $d$ in the first variable, it must be far from a univariate polynomial of degree $\le d$ for many values of $\beta$.

If you wish to test that $f$ is of degree $\le d$ in both variables, you can use the (highly non-trivial) result of Polischuk and Spielman from 1994, which is proved in Sections 2-5 in the following paper (see Theorem 9): http://cs-www.cs.yale.edu/homes/spielman/Research/holographic.html