随机算法 (Fall 2011)/Schwartz-Zippel

From EtoneWiki
Jump to: navigation, search

Polynomial identities

Consider the following problem:

  • Given as the input two multivariate polynomials and ,
  • check whether the two polynomials are identical, denoted .

Obviously, if are written out explicitly, the question is trivially answered in linear time just by comparing their coefficients. But in practice they are usually given in very compact form (e.g., as determinants of matrices), so that we can evaluate them efficiently, but expanding them out and looking at their coefficients is out of the question.

Example

Consider the polynomial

Show that evaluating at any given point can be done efficiently, but that expanding out to find all its coefficients is computationally infeasible even for moderate values of .

Here is a very simple randomized algorithm, due to Schwartz and Zippel. Testing is equivalent to testing , where .

Algorithm (Schwartz-Zippel)
  • pick independently and uniformly at random from a set ;
  • if then return “yes” else return “no”;

This algorithm requires only the evaluation of at a single point. And if it is always correct.

In the Theorem below, we’ll see that if then the algorithm is incorrect with probability at most , where is the maximum degree of the polynomial .

Theorem (Schwartz-Zippel)
Let be a multivariate polynomial of degree defined over a field . Fix any finite set , and let be chosen independently and uniformly at random from . Then
Proof.
The theorem holds if is a single-variate polynomial, because a single-variate polynomial of degree has at most roots, i.e. there are at most many choices of having , so the theorem follows immediately.

For multi-variate , we prove by induction on the number of variables .

Write as

where is the largest exponent of in . So by our definition of , and its degree is at most .

Thus by the induction hypothesis we have that .

Conditioning on the event , the single-variate polynomial has degree and , thus

.

Therefore, due to the law of total probability,