The Schwartz-Zippel lemma states that for a nonzero polynomial p of total degree d over a field F, if we evaluate p at a uniformly random point from S^n (where S is a subset of F), then Pr[p(r_1,...,r_n) = 0] <= d/|S|. Why is the total degree (not the individual variable degrees) the relevant parameter?
AIndividual variable degrees are always equal to the total degree
BThe lemma proceeds by induction on the number of variables: fix all but one variable, the resulting univariate polynomial has degree at most d and hence at most d roots in S, and the inductive step accounts for the cases where the leading coefficient (a polynomial in fewer variables) vanishes
CThe total degree bounds the number of monomials, and each monomial can vanish independently
DThe lemma only works for univariate polynomials, where total degree equals the single variable's degree
The proof of Schwartz-Zippel uses induction on the number of variables n. Write p(x_1,...,x_n) = sum_{i=0}^{k} x_1^i * q_i(x_2,...,x_n) where k <= d. The leading coefficient q_k is a nonzero polynomial of total degree at most d-k in n-1 variables. By induction, Pr[q_k(r_2,...,r_n) = 0] <= (d-k)/|S|. When q_k does not vanish, p becomes a nonzero univariate polynomial of degree at most k in x_1, which has at most k roots, so Pr[p = 0 | q_k != 0] <= k/|S|. By the law of total probability: Pr[p = 0] <= (d-k)/|S| + k/|S| = d/|S|. The total degree naturally arises from the inductive decomposition.
Question 2 True / False
Freivalds's algorithm verifies whether AB = C for three n x n matrices using O(n^2) time and O(1) error probability. It works by checking ABr = Cr for a random binary vector r.
TTrue
FFalse
Answer: True
Freivalds's algorithm: choose r uniformly from {0,1}^n, compute ABr (first Br in O(n^2), then A(Br) in O(n^2)) and Cr in O(n^2), check if they're equal. If AB = C, the check always passes. If AB != C, then D = AB - C is nonzero, so Dr != 0 with probability at least 1/2 (each entry of Dr is a polynomial of degree 1 in the r_i's, and by Schwartz-Zippel with d=1 and |S|=2, Pr[Dr = 0] <= 1/2). Repeating k times with independent random vectors reduces the error to 2^(-k). The total time is O(kn^2), compared to O(n^(2.37)) for actually computing AB. This is one of the simplest and most elegant applications of Schwartz-Zippel.
Question 3 Short Answer
Explain how Edmonds used polynomial identity testing to reduce the perfect matching problem to testing whether a polynomial is identically zero.
Think about your answer, then reveal below.
Model answer: Edmonds defined the Tutte matrix T of a graph G: for each edge (i,j) with i < j, set T[i,j] = x_{ij} (a formal variable) and T[j,i] = -x_{ij}, with all other entries 0. He proved that G has a perfect matching if and only if det(T) is not identically zero as a polynomial in the x_{ij} variables. To test this: by Schwartz-Zippel, substitute random values from a field of size >= 2n for each x_{ij} and compute the determinant numerically. If det(T) != 0 (which happens with probability >= 1/2 when a perfect matching exists), report 'matching exists.' If det(T) = 0, report 'no matching.' This gives a co-RP algorithm for perfect matching. Lovász later noted this also works for the Tutte matrix over finite fields.
The Tutte matrix is a skew-symmetric matrix whose determinant (the square of the Pfaffian) is a nonzero polynomial precisely when a perfect matching exists. Each term in the determinant expansion corresponds to a collection of cycles covering all vertices, and the terms corresponding to perfect matchings survive while others cancel due to the skew-symmetry. This algebraic encoding of a combinatorial problem, combined with Schwartz-Zippel for efficient testing, is one of the most beautiful connections between algebra and combinatorics.
Question 4 Multiple Choice
Derandomizing PIT (finding a deterministic polynomial-time algorithm for polynomial identity testing) would imply proving circuit lower bounds. Why does this connection exist?
APIT is NP-hard, so derandomizing it would prove P = NP which implies circuit lower bounds
BKabanets and Impagliazzo (2004) showed that a deterministic polynomial-time PIT algorithm implies either NEXP does not have polynomial-size arithmetic circuits, or the permanent does not have polynomial-size arithmetic circuits — both are major open circuit lower bounds
CPIT can simulate any Boolean circuit, so a fast PIT algorithm would directly compute circuit lower bounds
DDerandomizing PIT requires the PCP theorem, which itself implies circuit lower bounds
The Kabanets-Impagliazzo result establishes a remarkable barrier: you cannot derandomize PIT without proving new circuit lower bounds. Specifically, if PIT has a deterministic polynomial-time algorithm, then either (a) the permanent cannot be computed by polynomial-size arithmetic circuits (a major conjecture in algebraic complexity), or (b) NEXP is not contained in P/poly (a Boolean circuit lower bound far beyond current knowledge). Conversely, sufficiently strong circuit lower bounds imply derandomization of PIT via the Nisan-Wigderson generator framework. This tight connection means that PIT derandomization and circuit lower bounds are essentially equivalent problems — progress on either would imply progress on the other.
Question 5 Short Answer
Schwartz-Zippel works over any field, but for computational purposes, which field is typically used and why?
Think about your answer, then reveal below.
Model answer: Typically a prime field F_p (integers mod p) for a prime p > 2d, or the rationals. Over F_p, field operations (add, multiply, inverse) take O(log^2 p) time and the evaluation set S = F_p has |S| = p, giving error probability at most d/p. Choosing p >= 2d gives error <= 1/2 per trial. For multivariate polynomials given as arithmetic circuits, evaluation at a point takes time proportional to the circuit size. Working over a finite field avoids the integer blowup problem that occurs over Z or Q: intermediate values in the circuit could have exponentially many bits over Z, but over F_p all values are bounded by p. For the Tutte matrix application (perfect matching), a random prime p = O(n^2) suffices, and determinant computation over F_p takes O(n^3) field operations via Gaussian elimination.
The choice of field is a practical consideration that Schwartz-Zippel abstracts away. Finite fields give bounded arithmetic, random elements are easy to generate, and the error probability d/|F_p| is controllable by choosing p large enough. Extension fields GF(2^k) are used when characteristic-2 arithmetic is preferred.