Opening Multivariate Polynomials and the Schwartz Zippel Lemma
Multivariate Polynomials and the Schwartz Zippel Lemma
- Length
- 18 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Formal polynomials versus computed functions
Multivariate polynomials map multiple field elements into a single field element, and formal polynomials must be distinguished from the functions they compute. Non-zero polynomials can evaluate to zero everywhere, such as in finite fields, which allows reduction of variable degrees below . The Schwartz-Zippel lemma establishes that non-zero multivariate polynomials rarely evaluate to zero on random inputs, depending on their total degree and the field size. Lovász uses this lemma and matrix determinants to test for bipartite perfect matchings in parallel.

Your comment is kept while you sign up.Sign in
States the Schwartz-Zippel lemma, even for small fields, and applies it to Lovász's parallel perfect-matching test.
Multivariate polynomials map multiple field elements into a single field element, and formal polynomials must be distinguished from the functions they compute. Non-zero polynomials can evaluate to zero everywhere, such as in finite fields, which allows reduction of variable degrees below . The Schwartz-Zippel lemma establishes that non-zero multivariate polynomials rarely evaluate to zero on random inputs, depending on their total degree and the field size. Lovász uses this lemma and matrix determinants to test for bipartite perfect matchings in parallel.
This lecture
Lecture 30 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.