Abstract
The polynomial identity testing problem is to decide whether a given succinct algebraic expression simplifies to the zero expression. This problem has a simple randomized algorithm, and derandomizing this algorithm is analogous to constructing pseudorandom generators fooling boolean computation.
We will discuss a recent line of work derandomizing polynomial identity testing for the restricted class of expressions known as "read-once oblivious algebraic branching programs". Pseudorandom generators for the analogous boolean notion are fundamental, as they correspond to derandomization of randomized logspace computations (RL). Further, research into such generators has had many connections to well-studied objects such as expanders, extractors, and k-wise independent hash functions.
Likewise, the work on derandomizing "algebraic RL" has connections to linear-algebraic pseudorandomn objects such as rank-extractors and subspace-designs, which themselves have connections to list-decodable codes and dimension expanders. We will discuss the known results for derandomizing "algebraic RL", the various connections to other pseudorandom objects, and highlight the analogy with boolean pseudorandomness.