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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\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, 2012 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, 2012 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.