We intend to discuss the second part (Theorem 4) of the recent paper
"Bootstrapping variables in algebraic circuits" by Agrawal, Ghosh, Saxena
(STOC'18). Last time, we discussed depth-reduction result of AV08 and
realized that polynomial time PIT algorithm for just depth-4 circuits
gives us a quasi-polynomial time PIT algorithm for general circuits. In
other words, (poly(s), poly(s))-hsg (hitting set generator) for a size-s
depth-4 circuit is sufficient for the PIT problem.
Theorem 4 of AGS'18 further strengthens this result, stating that an
(poly(s), O( s^(n/2)/log^2(s) ) )-hsg for a polynomial computed by size-s
depth-4 circuit over a constant number of variables - n >= 3 implies a
quasi-polynomial time algorithm for general circuits. We note that
(poly(s), O(s^n)-hsg is trivial, and we only need to find a hitting set
whose size is slightly less than s^(n/2).