Derandomization via Robust Algebraic Circuit Lower Bounds
summary
Shows that depth-3 powering formulas imply a deterministic black-box identity test by turning a known exponential lower bound for the monomial x1 x2 ... xn into a robust statement: the partial-derivatives complexity measure is stable under lexicographic leading-monomial error, so any small sum-of-powers formula has its value determined by quasi-polynomially many monomials each depending on very few variables. That yields a quasi-polynomial-size hitting set and deterministic PIT; a truly polynomial-size hitting set remains open.
AI-written summary · about