Algebraic Complexity Seminar

Hardness versus Randomness in Algebraic Complexity Theory

In computational complexity theory there are two important strands of research.  "Hardness" refers to the task of exhibiting explicit functions which are hard to compute.  "Randomness" refers to the task of designing sequences of pseudorandom numbers that no efficient algorithm can distinguish from random numbers (and this in particular can be used to derandomize algorithms). Somewhat surprisingly, it was established in the 1980's that these two types of questions are essentially the _same_ question, a phenomenon now known as "hardness versus randomness".

In this talk, we will demonstrate this phenomenon in algebraic complexity theory. In particular, we will show that given any explicit hitting set for small algebraic circuits (a sequence of numbers that must yield a non-zero evaluation point to any non-zero polynomial) one can construct a polynomial which cannot be computed by a small circuit. Perhaps more interesting, we will show the converse: given any polynomial that is hard to compute you can construct a small hitting set, and in particular construct efficient deterministic algorithms to test whether an algebraic circuit computes the zero polynomial.