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 non-zero value at some point on an n-dimensional grid Sn with side length |S| > s . This gives 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 ε > 0 be a constant. For a sufficiently large constant n and all s ≥ n, if we have an explicit hitting set of size (s+1)n-ε for the class of n-variate degree s polynomials that are computable by algebraic circuits of size s, then for all large s, we have an explicit hitting set of size sexp(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 who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most (sn0.5-ε) (where ε > 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 Ramprasad Saptharishi.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
