2
$\begingroup$

In the Schwartz–Zippel algorithm for bounded error probabilistic polynomial identity testing, the main theorem is the following:

For a non-zero multivariate polynomial $p(x_1,...,x_n)$ of total degree $d \ge 0$ over a field, $F$. Let $S$ be a finite subset of $F$ and let $r_1, r_2, ..., r_n$ be selected at random independently and uniformly from $S$. Then

$$\Pr[p(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$$

The proof is short and can be read on the wiki page linked above. What I am having trouble understanding is the requirements on the sampling of values to test the polynomial. For example if

$$p(x,y,z) = xz-yz$$

then testing only values of the form $(a,a,a)$ would not be sufficient. However, for that polynomial, or indeed any ternary polynomial with degree in each individual variable no more than 1, it is okay to randomly equate two of the variables during testing (using test values of the form $(a,b,b), (b,a,b), (b,b,a)$ will allow testing if the polynomial is zero).

So my question is:

  • Where does the proof implicitly rely on the requirement of the values being "selected at random independently and uniformly"?
  • Is it known in what cases this can be relaxed?
    For example, considering polynomials where the degree in each individual variable is no more than 1, can this restriction be used to extend the example above with duplicate variable values to polynomials with more than three variables?
$\endgroup$
  • $\begingroup$ Uniform sampling is used in the base case, at least... (and in the inductive step, since it reduces it to a univariate polynomial after picking $r_2,\dots,r_n$). $\endgroup$ – Clement C. Jul 28 '16 at 4:51
  • $\begingroup$ @ClementC.I can see where they are assuming uniform sampling in the base case, but I don't see where the "independence" of the variables comes in for the inductive step. Either way, the trilinear polynomial example shows that the independence isn't strictly necessary in some cases. It would be nice to understand this better. $\endgroup$ – JustThinking Jul 29 '16 at 14:03

Your Answer

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

Browse other questions tagged or ask your own question.