Polynomial identity testing (PIT) is the algorithmic task of determining whether a given polynomial is identically zero. The ``Schwarz-Zippel lemma'' (credited to Ore, DeMillo, Lipton, Schwarz and Zippel) gives us that any nonzero polynomial of degree d on n variables evaluates to a nonzero value on some point in the n dimensional grid [d+1] x ... x [d+1]. Hence this grid forms an exponential sized ``hitting set'' for the class of n-variate polynomials of degree d.
For the class of n-variate, degree-d polynomials that have algebraic formulas of size s; a hitting set of size poly(n,d,s) is known to exist. However, constructing an explicit hitting set of any non-trivial size remains an open problem. In this talk, we will see the following surprising result. Suppose for some constant $n$ and all $d \leq s$, we have an explicit hitting set of size $s^{(n - 1)}$ for $n$- variate, degree-$d$ polynomials that have formulas of size $s$. Then for all $s$, we have an explicit hitting set of size $s^{tiny(s)}$ for $s$-variate, degree-$s$ polynomials that have formulas of size $s$. Here $tiny(s) = exp(exp(log^{*}s))$, which grows barely faster than a constant. Arguments in the proof will be fairly elementary and hence very little background in algebra or algebraic complexity will be assumed for the talk (joint work with Mrinal Kumar (Simons Institute, UCB) and Ramprasad Saptharishi).
