Avi Wigderson

## Derandomization of Probabilistic Logspace (The Nisan Variations)

Avi Wigderson
chool of Mathematics, Institute for Advanced Study
March 5, 2013 - 10:30am

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

## Derandomizing BPL?

Avi Wigderson
School of Mathematics, Institute for Advanced Study
February 26, 2013 - 10:30am

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.

## Local Correction of Codes and Euclidean Incidence Geometry

Avi Wigderson
March 5, 2012 - 2:00pm

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

## Randomness and Pseudo-randomness

Avi Wigderson
October 5, 2011 (All day)

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

Avi Wigderson
May 25, 2010 - 10:30am

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.

## PMSP - Expander graphs: Applications and combinatorial constructions II

Avi Wigderson
June 15, 2010 - 11:00am

## PMSP - Expander graphs: Applications and combinatorial constructions I

Avi Wigderson
June 15, 2010 - 9:00am

## Representation Theory and Expansion in Groups I

Avi Wigderson
January 26, 2010 - 10:30am

Avi Wigderson