5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does the (first) test work when the degree of the second variable is high? That is, say $f(x,y) = x^{q-2} (y -1)(y-2)\cdots(y-q+2)$, won't we can a low-degree polynomial for almost every random value of $f(\cdot, \beta)$? $\endgroup$ – user887 Oct 18 '12 at 13:00
  • 1
    $\begingroup$ In this example, the function is quite close to the zero polynomial, so it does not violate the test. Remember that the test is only required to reject functions that are far from every polynomial with degree d in the first variable. $\endgroup$ – Or Meir Oct 18 '12 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy