Lecture 31: 04/13/2012

A recap of Wednesday’s material at the beginning. We changed our definition of the degree of a multivariable polynomial slightly to make the proof of the Schwartz-Zippel Theorem a bit simpler.

Let f(x_1, …, x_n) be a polynomial in n variables from some field F.

A deterministic algorithm works like this:
Fix d to be the degree of f.

Choose d+1 values of each x_i for 1 <= i 1, and evaluate f(x) for x \in S. If f(x) = 0, then there’s at most a 1/k probability the function is identically zero. If we repeat this test a few times using elements selected uniformly at random from S, we get a pretty high probability of obtaining the correct answer.

If we extend to multivariate functions, we still choose random elements from a set S of size k*d from the field F where the polynomial is defined. However, we now evaluate f(x_1, …, x_n) for a randomly chosen tuple from S^n. If f(x_1, …, x_n) = 0, we get the same bound of at most 1/k probability of f being identically zero.

Now for another cool application of testing polynomials. Suppose we have a graph G and we want to know if there exists a perfect matching.

A matching is a 1-regular subgraph of G. A perfect matching is a 1-regular spanning subgraph of G. All this means is we pair up vertices where every pair of vertices share an edge, and every vertex appears in exactly one pair.

How do we do this? Well we can look for obvious signs of not having a perfect matching, such as having an odd number of vertices. Ok, but what if I have an even number of vertices? Try all the matchings! Brute force is always the way to go (just kidding).

There’s a deterministic algorithm that runs in O(m sqrt(n)) time, but can we do better using randomization? Yes!

We assign every edge a variable and form an adjacency matrix of the graph G. However, let’s orient the edges arbitrarily and every time we have a 1 or -1, we replace it with the variable of that edge.

Now, we compute the determinant symbolically and if the polynomial is non-zero, it tells us the perfect matchings in the graph. However, computing determinants symbolically is hard, so we can accomplish the same thing by substituting random values of the variables and checking if the polynomial is zero.

Lecture 30: 04/11/2012

I hope the homework went (is going) well!

Tomorrow (today) we’ll be talking about totally different. We’re gonna dive into some randomized algorithms with the Schwartz-Zippel Lemma.

Try to look it up on the internet before class so you’re not totally lost but here’s some basics:

We have a polynomial a_0 + a_1 x + … + a_d x^d that we’d like to check if it’s the zero-polynomial. That’s easy if we have it in coefficient form (just check if they’re all zero!). But what I give you something like (1 – x)(x + 2x^2 -19x^2)…(1 – x^3)? Well you’d have to multiply it all out (which takes exponential time) and check the coefficients.

😦

Schwartz-Zippel thought: what if you check that polynomial of degree d at some random point? If the value is not 0, then the polynomial can’t be the zero-polynomial. If it was zero, then there’s a good chance the polynomial is zero everywhere. So just repeat this test a bunch of times and if you always get zero, then its probably zero.

It gives us some cool applications so look forward to that!

What a great lecture today!

We first looked at the algebraic or deterministic way of determining if a polynomial is identically 0. You just have to check d+1 points for a polynomial of degree d. That’s great! So why bother with the randomized approach?

If you have a polynomial of degree d in two variables, then you have to check (d+1)(d+1) = d^2 + 2d + 1 points. Now it looks like our linear time algorithm is going to pay off.

We’ll look at how the probability bound changes when we go from one variable to several variables on Friday.

At the end, we looked at a very interesting application of this. We have two sets A and B. We want to check if they’re equal. Well, just sort ’em and check each element one by one. That takes O(n lg n) time, but what if n is huge??

Let A = [a_0, …, a_(n-1)] and B = [b_0, …, b_(n-1)]. Let P_A = (x – a_0)(…)(x – a_(n-1)) and P_B = (x – b_0)(…)(x – b_(n-1)). Now we can check if A = B by asking if (P_A – P_B) == 0. Using our probabilistic algorithm, we can pull this off in linear time and get the correct answer with very very very high probability.