I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms.

I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll see why each falls short of complete derandomization, BPL=L, hopefully motivating further work on this basic problem.

A classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem (and related ones), which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of combinatorial, algebraic and analytic tools.

Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff

Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics, gave a Friends Forum in October 2011, entitled Randomness and Pseudo-randomness.

The Stepanov method is an elementary method for proving bounds on the number of roots of polynomials. At its core is the following idea. To upper bound the number of roots of a polynomial f(x) in a field, one sets up an auxiliary polynomial F(x) , of (magically) low degree, which vanishes at the roots of f with high multiplicity. That appropriate F exits is usually proved by a dimension argument.

In this survey lecture (which will be continued), I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups.