Abstract
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial f(x1,...,xn) of degree at most s will evaluate to a nonzero value at some point on a grid S^n of in F^n with |S| > s . Thus, there is an explicit hitting set for all n-variate degree s, size s algebraic circuits of size (s+1)^n. We prove the following results: - Let eps > 0 be a constant. For a sufficiently large constant n and all s \geq n, if we have an explicit hitting set of size (s+1)^{n? eps} for the class of n-variate degree s polynomials that are computable by algebraic circuits of size s, then for all s, we have an explicit hitting set of size s^{exp exp (O(log*s)) for s-variate circuits of degree s and size s. That is, if we can obtain a barely non-trivial exponent compared to the trivial (s+1)^n sized hitting set even for constant variate circuits, we can get an almost complete derandomization of PIT. - The above result holds when "circuits" are replaced by "formulas" or "algebraic branching programs". This extends a recent surprising result of Agrawal, Ghosh and Saxena (STOC 2018) who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most (s^{n^{0.5 - eps}}) (where eps > 0 is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic branching programs and formulas. This is joint work with Mrinal Kumar and Anamay Tengse.