Hardness-Randomness Tradeoffs for Algebraic Computation

Abstract

The interplay between the question of proving lower bounds and that of derandomization, in various settings, is one of the central themes in complexity theory. In this survey, we explore this phenomenon in the area of algebraic complexity theory. Enroute, we discuss some of the classical results, as well as some recent ones, that establish a close connection between the question of proving algebraic circuits lower bounds and that of derandomizing polynomial identity testing. We also talk about an application of this machinery to the phenomenon of bootstrapping for polynomial identity testing and mention some open problems.