CPSC 536N: Randomized Algorithms

2011-12 Term 2

Lecture 9
Prof. Nick Harvey

1

University of British Columbia

Polynomial Identity Testing

In the first lecture we discussed the problem of testing equality of two bitstrings in a distributed setting.
We reduced that problem to the problem of testing whether a certain polynomial q is the zero polynomial.
That was our first glimpse of polynomial identity testing (PIT).
Let us now define the general PIT problem, while still being a bit vague. Given two multivariate
polynomials p(x1 , . . . , xn ) and q(x1 , . . . , xn ) over some field F, we would like to decide if they are equal.
Note that this is equivalent to deciding if their difference p − q is zero. This equivalent form is often
more convenient to think about because it only involves the single polynomial p − q. So we could also
define PIT to be: given a polynomial p(x1 , . . . , xn ) over some field F, decide if p is zero.
You might think this problem is rather dull and algebraic, but it actually captures many interestingand natural computational problems. For example, we’ve already seen that testing equality of strings
reduces to PIT (even univariate PIT). We’ll see another example in Section 2.
Next we discuss an important way in which our definition of PIT is too vague.
What is a zero polynomial? Our definition of PIT did not say precisely what it means for p to
be zero. There are two possible meanings, which lead to two different computational problems. Our
desired definition of PIT uses the second meaning.
• The Evaluates to Zero Everywhere (EZE) problem. Given a polynomial p(x1 , . . . , xn ) over F,
we must decide whether, for every choice of numbers y1 , . . . , yn ∈ F, the value of p(y1 , . . . , yn ) is
the number 0.
• The Polynomial Identity Testing (PIT) problem. Given a polynomial p(x1 , . . . , xn ), we canwrite it as a sum over monomials with various coefficients. For example, given p(x, y, z) = (x +2y)(3y − z), we can expand it into a sum of monomials asp(x, y, z) = 3xy + 6y 2 − xz − 2yz.
The problem is to decide whether, after expanding p into monomials, are all coefficients of thosemonomials equal to zero? If so, we say that p is the zero polynomial, or that it is identicallyzero.
It might never have occurred to you that EZE and PIT are different problems. If p is identically zerothen definitely it evaluates to zero everywhere. Is the converse true? Over any infinite field, like R orC, the converse is true: a polynomial evaluates to zero at every point if and only if it is identically zero.
But over finite fields the converse is not true, so EZE and PIT are different problems. For example, theunivariate polynomial p(x) = x2 + x over F2 is not identically zero but p(0) = 0 and p(1) = 1 + 1 = 0.
It is worth pointing out that trivial approaches do not solve these problems efficiently. The trivial approach for EZE is to exhaustively try every possible choice of numbers y1 , . . . , yn and evaluatep(y1 , . . . , yn ). This requires |F|n evaluations. The trivial approach for PIT is to explicitly expand the1polynomial into monomials, but if p has degree d then there can be
exponential in d.

n+d
d



such monomials, which is

Let me also clarify what is meant by the degree of a multivariate polynomial (or even monomial).
Qn
βi
A monomial is any expression of the form α · P
i=1 xi where α ∈ F and β1 , . . . , βn are non-negative
integers. The total degree of that monomial is i βi . The total degree of a polynomial is defined tobe the largest total degree of its monomials.
Our definitions of EZE and PIT are still vague in another important way.
How to represent a polynomial? What does it mean to be given a polynomial? One naturaldefinition is to allow p(x1 , . . . , xn ) to be presented as an explicit algebraic formula involving only thevariables x1 , . . . , xn , any numbers in F, parentheses, and the operations of addition, subtraction andmultiplication. For example, p(x1 , x2 ) = x1 · (x1 − 2 · x2 ).
Alternatively, we could allow p to be presented as a “black box”, meaning that we do not have an
explicit representation of p but our algorithms are allowed to evaluate p by plugging in any desired
numbers for x1 , . . . , xn . This is useful because we might have some weird representation for p that is
not an explicit formula. For example, let
1 x1 x21 . . . x1n−1
1 x2 x2 . . . xn−1 


2
2
.
..
p(x1 , . . . , xn ) = det 


.


..
2
n−1
1 xn xn . xn
Then p is actually a polynomial in x1 , . . . , xn of total degree at most n(n − 1). We can easily choose
numeric values for x1 , . . . , xn and evaluate p at that point simply by plugging those numbers into thematrix and computing the determinant numerically. But it might be the case that p does not have aconcise representation as an explicit formula. (InQ
this particular example the matrix is a Vandermondematrix, and the explicit formula p(x1 , . . . , xn ) = i<j (xi − xj ) is known.)
For our purposes, it does not matter whether the polynomial is given as an explicit formula or as a
black box. We discuss this issue further in Section 1.4.

1.1

Complexity Status

Unfortunately EZE is coNP-hard. There is a simple procedure to encode any 3SAT formula as apolynomial over F2 such that the polynomial evaluates to zero everywhere if and only if the formula isunsatisfiable.
The complexity status of PIT is much more interesting. We will show that there is a randomized algorithm to decide PIT. However, there is no known deterministic algorithm for deciding PIT. Furthermore,
if a deterministic algorithm existed then there would be remarkable consequences in complexity theory.

1.2

The Schwartz-Zippel Lemma

The main tool that we will use today is the Schwartz-Zippel lemma.
Lemma 1 Let p(x1 , . . . , xn ) be a polynomial of total degree d. Assume that p is not identically zero.
Let S ⊆ F be any finite set. Then, if we pick y1 , . . . , yn independently and uniformly from S,
Pr[ p(y1 , . . . , yn ) = 0 ] ≤
2

d
.
|S|

To help understand the lemma, consider the case of polynomials over R. The theorem says that if we
evaluate p at a random point, then we have small probability of seeing a root. Does that mean thatpolynomials over R have finitely many roots? No! Consider the polynomial p(x1 , x2 ) = x1 which has
total degree d = 1. It has infinitely many roots because setting x1 = 0 and x2 to anything gives a root.
However, if we fix S = {0, 1} and randomly choose x1 , x2 ∈ S then our probability of seeing a root isexactly 1/2, which matches the bound given by the Schwartz-Zippel lemma.
It is also worth noting that the conclusion of the theorem does not depend on n.
Proof: We proceed by induction on n.
The base case is the case n = 1, which is the univariate case we discussed in the first lecture. We
claimed that any univariate polynomial of degree d has at most d roots. (The reason is that any
univariate polynomial of degree d factors uniquely into at most d irreducible polynomials, each of which
has at most one root.) So, the probability that y1 is a root is at most d/|S|.
Now we assume the theorem is true for polynomials with n − 1 variables, and we prove it for those withn variables. The main idea is to obtain polynomials with fewer variables by factoring out the variable
x1 from p. Let k be the largest power of x1 appearing in any monomial of p. Thenp(x1 , . . . , xn ) =kX

xi1 · qi (x2 , . . . , xn ).

i=0

By our choice of k, the polynomial qk is not identically zero. Furthermore its total degree is at mostd − k, so by inductiond−kPr[ qk (y2 , . . . , yn ) = 0 ] ≤.
|S|
Define E1 to be the event “qk (y2 , . . . , yn ) = 0”.
Let us now randomly choose the values of y2 , . . . , yn and assume that the event E1 did not occur. Definef (x1 ) to be the univariate polynomialf (x1 ) =kX

xi1 · qi (y2 , . . . , yn ) = p(x1 , y2 , . . . , yn ).

i=0

Since E1 did not occur, the coefficient of xk1 in f is non-zero, so f is not identically zero. By the argumentof our base case,kPr[ f (y1 ) = 0 | ¬E1 ] ≤.
|S|Define E2 to be the event “f (y1 ) = 0”. By definition of f , E2 is equivalent to “p(y1 , . . . , yn ) = 0”.
We’re almost done. The goal of the lemma is to bound Pr[E2 ], and so far we’ve bounded Pr[E2 | ¬E1 ]and Pr[E1 ]. By a few manipulations, we get
Pr[E2 ] = Pr[E2 ∧ E1 ] + Pr[E2 ∧ ¬E1 ]= Pr[E2 ∧ E1 ] + Pr[E2 | ¬E1 ] · Pr[¬E1 ]≤ Pr[E1 ] + Pr[E2 | ¬E1 ]
k
d
d−k
≤
+
=
|S|
|S|
|S|
which finishes the proof. 2

3

1.3

Solving PIT

With the Schwartz-Zippel lemma in hand, we can easily solve PIT. Suppose we are given a polynomialp(x1 , . . . , xn ) of total degree d. Assume that d < |F|. (For more on this point, see Section 1.4.)
Our algorithm simply picks y1 , . . . , yn uniformly and independently from F (or if F is infinite, a suitably
large finite subset of F). If p(y1 , . . . , yn ) evaluates to a non-zero value, the algorithm announces that “pis not identically zero”. In this case we will never make an error: we have conclusive proof that p is not
identically zero. Otherwise, if p(y1 , . . . , yn ) = 0, the algorithm announces that “p is identically zero”.
In this case the Schwartz-Zippel lemma shows that probability of error is at most d/|F| < 1.
We can decrease the probability of error to any desired level by repeating the algorithm multiple times.
This is the amplification by independent trials trick. For example, even if d = |F| − 1, then repeating
the algorithm |F| times reduces the probability of failure to at most |F| − 1 |F|
|F|

1.4

≤



1 |F|
1−≤ 1/e.
|F|

Further Discussion of Complexity Status

Our randomized algorithm above assumed that p had total degree d < |F|. Under that assumption,
the Schwartz-Zippel lemma implies that any polynomial that evaluates to zero everywhere must be
identically zero. Therefore, under the assumption that d < |F|, the problems EZE and PIT are actuallyequivalent, so they can both be solved by our randomized algorithm. This also explains why EZE andPIT are equivalent for infinite fields.
It remains to discuss the case d ≥ |F|. In this case:• EZE is NP-hard as mentioned above.
• PIT in the black box model cannot be solved. This is because there are polynomials which are
not identically zero, but evaluate to zero everywhere (such as p(x) = x2 + x over F2 ) and thesecannot be distinguished from the identically zero polynomial.
• PIT in the explicit formula model is solvable! Since d ≥ |F|, the Schwartz-Zippel lemma does
not give any useful information about the number of roots. The trick is to use a field extensionof F. Any finite field F can be extended to larger finite field F0 which contains F as a subfield.
So instead of viewing p as a polynomial over F, we view it as a polynomial over a larger field F0
with d < |F0 |. This preserves the property of p being identically zero, so we can simply run ourrandomized algorithm for p over the field F0 .

2

Bipartite Matching

We conclude by describing using PIT to solve the Bipartite Matching problem.
Let G = (U ∪ V, E) be a bipartite graph, meaning that U and V are disjoint sets of vertices, and everyedge in E has exactly one endpoint in U and exactly one endpoint in V . A matching in G is a set ofedges that share no endpoints. A perfect matching in G is a set of edges M ⊆ E such that every
vertex is contained in exactly one edge of M .
4

Polynomial time algorithms are known to decide if G has a perfect matching, and even to construct sucha matching. We will give a randomized algorithm to decide if G has a perfect matching, by reducingthat problem to PIT.
Let A be the matrix whose rows are indexed by the vertices in U and columns are indexed by thevertices in V . The entries of A are:(xu,v
(uv ∈ E)
Au,v =,
0(uv 6∈ E)
where { xu,v : uv ∈ E } are distinct variables.
Claim 2 det A is identically zero if and only if G has no perfect matching.
Proof: By the Leibniz formula for determinants,XY
det A =
sign(π)Au,π(u) ,πu∈Uwhere the sum is over all bijections π : U → V and sign(π) is a function taking values in {+1, −1}
whose definition is irrelevant for our purposes.
The key observation is that a bijection from U to V is simply a pairing { (u, π(u)) : u ∈ U } of elementsin U and elements in V such that each vertex appears in exactly one pair. This is almost the sameas our definition of a perfect matching. If each of those pairs (u, π(u)) were an edge in E, then thatpairing would be exactly a perfect matching in G.
Q
Q
Conveniently, the monomial u∈U Au,π(u) tells us exactly when that happens. More precisely, u∈U Au,π(u)is a non-zero monomial if and only if π corresponds to a perfect matching in G. Furthermore, since allof these monomials involve distinct sets of variables, there can be no cancellations when we add up themonomials.
Q
Therefore u∈U Au,π(u) appears as a monomial in det A (possibly with a minus sign) if and only if πcorresponds to a matching in G. 2
This claim yields the following algorithm for testing if a bipartite graph has a perfect matching. Let F
be any field of size at least n2 . We can view det A as a polynomial over F since all coefficients of its
monomials are +1 and −1. Assign every variable xu,v a random value from F. Compute the numericdeterminant det A. If the determinant is zero, say “G has no perfect matching”. Otherwise, say “Ghas a perfect matching”. Since det A has degree n the Schwartz-Zippel lemma implies that the failure
probability of this algorithm is at most n/n2 < 1/n.

5