Partial Derandomization of Polynomial Identity Checking (I)

(To Ryan and Venkat: my post is getting too long so I'm breaking it into two (hopefully not three) parts and the second part will come out tomorrow...)

Checking multivariate polynomial identities is a problem central to algorithm design and complexity theory.

I didn't inline a formal definition in the previous sentence, because there's a catch in defining the problem. A polynomial $P(x_1,...,x_n)$ (say, in $F[x_1,...,x_n]$ for some field $F$) can be viewed as, at least, two things: syntactically, it is just a formal expression recursively built up from variables, coefficients from $F$, arithmetic operators and parentheses; semantically, it is a function from $F^n$ to $F$. Correspondingly, when we say a polynomial is identical to zero, we can have two different meanings:

1. It is indeed the zero element in the ring $F[x_1,...,x_n]$. Namely, when written in sparse form (that is, when parentheses are no longer needed), all coefficients turn out to be zero.
2. It is a constant function that maps all the points in $F^n$ to $0\in F$.

The two definitions coincide only over an infinite field $F$ (reason: a syntactically non-zero polynomial can not vanish on all the points in $F^n$ (but note that it can definitely vanish on an infinite number of points, some online notes are wrong about this), since you can fix values to $n-1$ variables and get a univariate polynomial which can only have finitely many roots (less or equal than its degree). For a finite field of size $q$, the polynomial $(x^q-x)\in F[x]$ vanishes on every point in $F$ (reason: the nonzero elements are in a cyclic group under multiplication, obeying Lagrange's theorem).

We fix definition #1. If you need, two reasons can be provided:
1. For definition #2, the problem is coNP-complete over finite fields. It's in coNP since you can decide its complement language by checking certificates for their nonzero-ness. It's complete since Boolean tautologies are just polynomials that are always evaluated to 1 over the finite field of size 2.
2. Applications: Biparitite matching, IP=PSPACE, etc.

Now the problem is clear: given a multivariate polynomial $P(x_1,...,x_n)\in F[x_1,...,x_n]$, we would like to decide whether $P(x_1,...,x_n)=0\in F[x_1,...,x_n]$. Next we need to decide the description format of the input polynomials. In the trivial case, polynomials can be given in sparse form and you just take a look at the coefficients. Of course that shouldn't be what we are concerned about here, since expanding polynomials easily takes exponential time. Rather, we take the black-box model of the polynomials, which is just something that efficiently evaluates the polynomial given any point in $F^n$. The only parameters of the polynomial that we have access are: the number of variables $n$, and the highest degree on each variable $d_i, i\in \{1,...,n\}$. Note that if we are allowed to know other parameters, the problem can be different.

So (Too) much for the preparation. The problem was given a randomized polynomial time algorithm first by Schwartz-Zippel. Twenty years after that, Chen-Kao gave a partial derandomization of Schwartz-Zippel's algorithm (i.e., reduced the number of random bits needed in the algorithm) for polynomials with integer coefficients. Later, Lewin-Vadhan, which will be the focus of (the coming second part of) my post, generalized Chen-Kao's method to the problem in its full generality, and proved the optimality of the number of random bits used under the given model (blackbox, same parameters). As mentioned in class, whether the algorithm can be fully derandomized is open.