Multivariate polynomials

Now, we will consider polynomials that have more than one variable. With a single variable, everything is quite intuitive. For instance, univariate polynomials of degree $d$ have at most $d$ roots, but this is false when we have multivariate polynomials (e.g., $f(x,y) = x-y$ is a degree one polynomial but has infinitely many roots). However, you will see that we can still take advantage of the low-degree polynomials in some way and that multivariables allow you to encode much more complex problems as polynomials.

📄️ Matrix multiplication testing

We start with a simple computational problem. Given three $n$-by-$n$ matrices $A,B,C$, our goal is to design an algorithm that checks whether $A B = C$. Notice that one way to solve this problem is by performing the matrix multiplication $A B$ and checking whether the result is the same as $C$. This takes $O(n^{\omega})$ time where $\omega$ is defined as the minimum value $\tau$ such that matrix multiplication can be done in $O(n^{\tau})$ time. The current best known value is $\omega \approx 2.371\ldots$ (proving or disproving that $\omega =2$ is a long-standing open question).

📄️ The Schwartz-Zippel Lemma

We will now look at a generalization of the above technique. The key idea is that the equation $(AB-C)\textbf$ (as considered in the previous section) is a polynomial $p(x1,\ldots, xn)$ of degree one, and the problem we are solving is to check whether this polynomial is the zero polynomial or not.

📄️ Perfect matching detection

We consider the following problem: Given a bipartite graph $G=(V,E)$ where $V = X \cup Y$ is a bi-partition and $|X|=|Y|=n$, our goal is to decide whether $G$ has a perfect matching.

📄️ Proof of Theorem 48 (Schwartz-Zippel Lemma)

We prove the theorem by induction on $n$ (the number of variables). When $n=1$, this is exactly the univariate case so the polynomial has at most $d$ roots, and therefore the probability of at most $d/|S|$ follows trivially.