Oftentimes, we might want to test that two polynomials are equal. Many problems can be encoded as the equality of two polynomials—as we are going to see later, the existence of a bipartite matching in a graph can be phrased by saying that a certain determinant polynomial is nonzero.

**1. Polynomials**

Testing that a polynomial in the usual encoding (as a list of coefficients) is nontrivial is, of course, a trivial task, one that a simple linear scan would accomplish. But, as we are going to see, the polynomials that one may wish to test for being nonzero need not be presented to us in this form. Rather, they may come to us recursively.

Here is one example. We can think of a boolean formula as a tree of gates. Each gate has one or two ends flowing into it and one edge leaving. The gates can be and, or, and not (in the last case, one edge flows in). Given the boolean inputs that flow into it, the gate outputs true or false according to the usual formulas. Finally, there are *input gates* where one can choose to place either true or false, and one final output gate at the end. We can connect the output lines of gates as input lines of new gates, and combining them, we can get a boolean formula.

Similarly, we could present a polynomial as a tree of gates. Each gate is either addition or multiplication; the input gates can hold variables or constants. When we put the inputs in, we get a polynomial. But in a gate of size , the total output (because of all the multiplications) could be exponential in the degree! The upshot of this is that, if we are presented with a polynomial in the form of a tree of gates, we find that actually evaluating the coefficients of the polynomial may be an exponential-time, intractable task. But if we wanted to evaluate the polynomial at a specific value, and modulo some (not too large) value, we could do it efficiently, by working through the gates *and* reducing mod the value at each step to keep things from getting too large.

So we get the idea that to test whether a polynomial is nonzero, it may be useful, instead of expanding it out, to evaluate it on some specific values, in which case we will get a *probabilistic* algorithm. However, nonzero polynomials have roots, and to make such an approach of testing work, we will have to randomize things.

**2. The Schwarz-Zippel lemma**

The Schwarz-Zippel lemma gives a bound on the probability that a multivariate polynomial over a finite field will have roots in a given set.

Lemma 1 (Schwarz-Zippel)Let be a field, a nonzero polynomial of total degree . Suppose is a finite subset. Then if the tuple is randomly chosen from , then the probability that is at most .

We are going to prove this by induction on the number of variables. When , this is just the statement that a one-variable polynomial of degree can have at most roots (if it is nonzero). Now suppose the result proved for . We can write

where involves only the first variables and has degree . Let be the largest index such that is not identically zero. Then at the pairs such that , there will be at most choices of to make vanish. So we have

By induction, this is at most

which proves the lemma.

**3. Polynomial identity testing**

So, we are given the following situation. We have two polynomials expressed in some funny form (like via an arithmetic circuit), and these polynomials may have very large degree (exponential in the input size ). However, if is a reasonable number (of size polynomial in ), we can evaluate the polynomials mod in polynomial time. This is the case for the boolean circuit, for instance.

Then actually computing the coefficients cannot be done efficiently because the degree is exponential. Even computing the value of by themselves is infeasible because the output may need exponentially many bits! However, we can compute their values mod any small . From this, we want a probabilistic algorithm that will tell us whether or not.

Here is the idea. Let us suppose we know that the degrees of are at most (which is generally exponential in ). Given this, choose randomly in . (Then has bits, so we are ok.) Choose inputs randomly in . Then we evaluate mod on . This can be done in polynomial time. If this is zero, output that are equal; if not, output that they are unequal.

What we need to show is that if , then there is a high probability that the algorithm will output “unequal.” Well, there is a high probability that as *integers* by the Schwarz-Zippel lemma. Suppose that these two values are indeed unequal; then the claim is that for most choices of , we will get something nonzero mod . But is , so it has prime factors. Conversely, there are about possible primes in . So the probability that is prime and does not divide is at least

which is comparable to or comparable to . It follows that the probability that our algorithm falsely concludes that two unequal polynomials are equal is about . Granted, this is as . So, to make it better, we just run it times or so; then the probability that our algorithm fails is small, while it still runs in polynomial time.

I should probably mention that I’m drawing the material from these computer science posts primarily from Papadimitriou’s and Arora-Barak’s textbooks on complexity theory, and some of my (limited) understanding of basic algorithms comes from CLRS (as well as the course I am taking).

## Leave a Reply