2
The Power of Randomness
2.1 Polynomial Identity Testing
Before we study the derandomization of randomized algorithms, we will need some algorithms to
derandomize. This section introduces one such algorithm. It solves the following computational
problem.
Computational Problem 2.1. Identity Testing: given two multivariate polynomials,
p(x1 , . . . , xn ) and q(x1 , . . . , xn ), decide whether p = q.
This definition requires some clarification. Specifically, we need to say what we mean by:
• “polynomials”: A (multivariate) polynomial is an finite expression of the form
X
p(x1 , . . . , xn ) = ci1 ,...,in xi11 xi22 · · · xinn .
i1 ,...,in ∈N
We need to specify what space the coefficients of the polynomials will come from; they
could be the integers, reals, rationals, etc. In general, we will assume that the coefficients
are chosen from a field (a set with addition and multiplication, where every nonzero
element has a multiplicative inverse) or more generally an (integral) domain (where the
product of two nonzero elements is always nonzero). Examples of fields include Q (the
rationals), R (the reals), Zp (integers modulo p) where p is prime. An integral domain
that is not a field is Z (the integers), but every integral domain is contained in its field of
fractions, which is Q in the case of Z. Zn for composite n is not even an integral domain.
We remark that there does exist a finite field Fq of size q = pk for every prime p and
positive integer k, and in fact this field is unique (up to isomorphism); but Fq is only
equal to Zq in case q is prime (i.e. k = 1). For more background on algebra, see the
references in the chapter notes.
For a polynomial p(x1 , . . . , xn ) = i1 ,...,in ci1 ,...,in xi11 xi22 · · · xinn , we define its degree (a.k.a.
P
total degree) to be the maximum sum of the exponents i1 + · · · + in over its monomials
6
, with nonzero coefficients ci1 ,...,in . Its degree in xj is the maximum of ij over its monomials
with nonzero coefficients.
• “p = q”: What does it mean for two polynomials to be equal? There are two natural
choices: the polynomials are the same as functions (they have the same output for ev-
ery point in the domain), or the polynomials are the same as formal polynomials (the
coefficients for each monomial are the same).
These two definitions are equivalent over the integers (or more generally over infinite
domains), but they are not equivalent over finite fields. For example, consider
Y
p(x) = (x − α).
α∈F
for a finite field F.1
It is easy to see that p(α) 6= 0 for all α ∈ F, but p 6= 0 as a formal
polynomial. For us, equality refers to equality as formal polynomials.
• “given”: What does it mean to be given a polynomial? There are several possibilities
here:
(1) As a list of coefficients: this trivializes the problem of Identity Testing, as we
can just compare.
(2) As an “oracle”: a black box that, given any point in the domain, gives the value
of the polynomial.
(3) As an arithmetic formula: a sequence of symbols like (x1 +x2 )(x3 +x7 +6x5 )x3 (x5 −
x6 ) + x2 x4 (2x3 + 3x5 ) that describes the polynomial. Observe that while we can
solve Identity Testing by expanding the polynomials and grouping terms,
but the expanded polynomials may have length exponential in the length of the
formula, and thus the algorithm is not efficient.
More general than formulas are circuits. An arithmetic circuit consists of a di-
rected acyclic graph, consisting of input nodes, which have indegree 0 and are
labeled by input variables or constants, and computation nodes, which have in-
degree 2 and are labelled by operations (+ or ×) specifying how to compute a
value given the values at its children; one of the computation nodes is designated
as the output node. Observe that every arithmetic circuit defines a polynomial in
its input variables x1 , . . . , xn . Arithmetic formulas are equivalent to arithmetic
circuits where the underlying graph is a tree.
The randomized algorithm we describe will work for both the 2nd and 3rd formulations above (or-
acles and arithmetic circuits/formulas). It will be convenient to work with the following equivalent
version of the problem.
Computational Problem 2.2. Identity Testing (reformulation): Given a polynomial
p(x1 , . . . , xn ), is p = 0?
That is, we consider the special case of the original problem where q = 0. Any solution for
the general version of course implies one for the special case; conversely, we can solve the general
version by applying the special case to the polynomial p0 = p − q.
1 When expanded and terms are collected, this polynomial p can be shown to simply equal x|F| − x.
7
, Algorithm 2.3 (Identity Testing).
Input: A multivariate polynomial p(x1 , . . . , xn ) of degree at most d over a field/domain F.
(1) Let S ⊆ F be any set of size 2d.
R
(2) Choose α1 , . . . , αn ← S.
(3) Evaluate p(α1 , . . . , αn ). If the result is 0, accept. Otherwise, reject.
It is clear that if p = 0, the algorithm will always accept. The correctness in case p 6= 0 is based
on the following simple but very useful lemma.
Lemma 2.4 (Schwartz–Zippel Lemma). If p is a nonzero polynomial of degree d over a field
(or integral domain) F and S ⊆ F, then
d
Pr [p(α1 , . . . , αn ) = 0] ≤ .
R
α1 ,...,αn ←S |S|
In the univariate case (n = 1), this amounts to the familiar fact that a polynomial with coeffi-
cients in a field and degree d has at most d roots. The proof for multivariate polynomials proceeds
by induction on n, and we leave it as an exercise (Problem 2.1).
By the Schwartz-Zippel lemma, the algorithm will err with probability at most 1/2 when p 6= 0.
This error probability can be reduced by repeating the algorithm many times (or by increasing
|S|). Note that the error probability is only over the coin tosses of the algorithm, not over the
input polynomial p. This is what we mean when we say randomized algorithm; it should work on
a worst-case input with high probability over the coin tosses of the algorithm. Algorithms whose
correctness (or efficiency) only holds for randomly chosen inputs are called heuristics, and their
study is called average-case analysis.
Note that we need a few things to ensure that our algorithm will work.
• First, we need is a bound on the degree of the polynomial. We can get this in different ways
depending on how the polynomial is represented. For example, for arithmetic formulas,
the degree is bounded by the length of the formula. For arithmetic circuits, the degree is
at most exponential in the size (or even depth) of the circuit.
• We also must be able to evaluate p when the variables take arbitrary values in some
set S of size 2d. For starters, this requires that the domain F is of size at least 2d. We
should also have an explicit representation of the domain F enabling us to write down and
manipulate field elements (e.g. the prime p in case F = Zp ). Then, if we are given p as an
oracle, we have the ability to evaluate p by definition. If we are given p as an arithmetic
formula or circuit, then we can do a bottom-up, gate-by-gate evaluation. However, over
infinite domains (like Z), there is subtlety — the bit-length of the numbers can grow
exponentially large. Problem 2.4 gives a method for coping with this.
8
The Power of Randomness
2.1 Polynomial Identity Testing
Before we study the derandomization of randomized algorithms, we will need some algorithms to
derandomize. This section introduces one such algorithm. It solves the following computational
problem.
Computational Problem 2.1. Identity Testing: given two multivariate polynomials,
p(x1 , . . . , xn ) and q(x1 , . . . , xn ), decide whether p = q.
This definition requires some clarification. Specifically, we need to say what we mean by:
• “polynomials”: A (multivariate) polynomial is an finite expression of the form
X
p(x1 , . . . , xn ) = ci1 ,...,in xi11 xi22 · · · xinn .
i1 ,...,in ∈N
We need to specify what space the coefficients of the polynomials will come from; they
could be the integers, reals, rationals, etc. In general, we will assume that the coefficients
are chosen from a field (a set with addition and multiplication, where every nonzero
element has a multiplicative inverse) or more generally an (integral) domain (where the
product of two nonzero elements is always nonzero). Examples of fields include Q (the
rationals), R (the reals), Zp (integers modulo p) where p is prime. An integral domain
that is not a field is Z (the integers), but every integral domain is contained in its field of
fractions, which is Q in the case of Z. Zn for composite n is not even an integral domain.
We remark that there does exist a finite field Fq of size q = pk for every prime p and
positive integer k, and in fact this field is unique (up to isomorphism); but Fq is only
equal to Zq in case q is prime (i.e. k = 1). For more background on algebra, see the
references in the chapter notes.
For a polynomial p(x1 , . . . , xn ) = i1 ,...,in ci1 ,...,in xi11 xi22 · · · xinn , we define its degree (a.k.a.
P
total degree) to be the maximum sum of the exponents i1 + · · · + in over its monomials
6
, with nonzero coefficients ci1 ,...,in . Its degree in xj is the maximum of ij over its monomials
with nonzero coefficients.
• “p = q”: What does it mean for two polynomials to be equal? There are two natural
choices: the polynomials are the same as functions (they have the same output for ev-
ery point in the domain), or the polynomials are the same as formal polynomials (the
coefficients for each monomial are the same).
These two definitions are equivalent over the integers (or more generally over infinite
domains), but they are not equivalent over finite fields. For example, consider
Y
p(x) = (x − α).
α∈F
for a finite field F.1
It is easy to see that p(α) 6= 0 for all α ∈ F, but p 6= 0 as a formal
polynomial. For us, equality refers to equality as formal polynomials.
• “given”: What does it mean to be given a polynomial? There are several possibilities
here:
(1) As a list of coefficients: this trivializes the problem of Identity Testing, as we
can just compare.
(2) As an “oracle”: a black box that, given any point in the domain, gives the value
of the polynomial.
(3) As an arithmetic formula: a sequence of symbols like (x1 +x2 )(x3 +x7 +6x5 )x3 (x5 −
x6 ) + x2 x4 (2x3 + 3x5 ) that describes the polynomial. Observe that while we can
solve Identity Testing by expanding the polynomials and grouping terms,
but the expanded polynomials may have length exponential in the length of the
formula, and thus the algorithm is not efficient.
More general than formulas are circuits. An arithmetic circuit consists of a di-
rected acyclic graph, consisting of input nodes, which have indegree 0 and are
labeled by input variables or constants, and computation nodes, which have in-
degree 2 and are labelled by operations (+ or ×) specifying how to compute a
value given the values at its children; one of the computation nodes is designated
as the output node. Observe that every arithmetic circuit defines a polynomial in
its input variables x1 , . . . , xn . Arithmetic formulas are equivalent to arithmetic
circuits where the underlying graph is a tree.
The randomized algorithm we describe will work for both the 2nd and 3rd formulations above (or-
acles and arithmetic circuits/formulas). It will be convenient to work with the following equivalent
version of the problem.
Computational Problem 2.2. Identity Testing (reformulation): Given a polynomial
p(x1 , . . . , xn ), is p = 0?
That is, we consider the special case of the original problem where q = 0. Any solution for
the general version of course implies one for the special case; conversely, we can solve the general
version by applying the special case to the polynomial p0 = p − q.
1 When expanded and terms are collected, this polynomial p can be shown to simply equal x|F| − x.
7
, Algorithm 2.3 (Identity Testing).
Input: A multivariate polynomial p(x1 , . . . , xn ) of degree at most d over a field/domain F.
(1) Let S ⊆ F be any set of size 2d.
R
(2) Choose α1 , . . . , αn ← S.
(3) Evaluate p(α1 , . . . , αn ). If the result is 0, accept. Otherwise, reject.
It is clear that if p = 0, the algorithm will always accept. The correctness in case p 6= 0 is based
on the following simple but very useful lemma.
Lemma 2.4 (Schwartz–Zippel Lemma). If p is a nonzero polynomial of degree d over a field
(or integral domain) F and S ⊆ F, then
d
Pr [p(α1 , . . . , αn ) = 0] ≤ .
R
α1 ,...,αn ←S |S|
In the univariate case (n = 1), this amounts to the familiar fact that a polynomial with coeffi-
cients in a field and degree d has at most d roots. The proof for multivariate polynomials proceeds
by induction on n, and we leave it as an exercise (Problem 2.1).
By the Schwartz-Zippel lemma, the algorithm will err with probability at most 1/2 when p 6= 0.
This error probability can be reduced by repeating the algorithm many times (or by increasing
|S|). Note that the error probability is only over the coin tosses of the algorithm, not over the
input polynomial p. This is what we mean when we say randomized algorithm; it should work on
a worst-case input with high probability over the coin tosses of the algorithm. Algorithms whose
correctness (or efficiency) only holds for randomly chosen inputs are called heuristics, and their
study is called average-case analysis.
Note that we need a few things to ensure that our algorithm will work.
• First, we need is a bound on the degree of the polynomial. We can get this in different ways
depending on how the polynomial is represented. For example, for arithmetic formulas,
the degree is bounded by the length of the formula. For arithmetic circuits, the degree is
at most exponential in the size (or even depth) of the circuit.
• We also must be able to evaluate p when the variables take arbitrary values in some
set S of size 2d. For starters, this requires that the domain F is of size at least 2d. We
should also have an explicit representation of the domain F enabling us to write down and
manipulate field elements (e.g. the prime p in case F = Zp ). Then, if we are given p as an
oracle, we have the ability to evaluate p by definition. If we are given p as an arithmetic
formula or circuit, then we can do a bottom-up, gate-by-gate evaluation. However, over
infinite domains (like Z), there is subtlety — the bit-length of the numbers can grow
exponentially large. Problem 2.4 gives a method for coping with this.
8
