Series Title
" Some topics in computational complexity "  Abstract

Lecture 1 Abstract   Download Lecture
The power and weakness of randomness in computation.
Wednesday, Jan 9, 2008 2:00 PM, MS 6627

Lecture 2 Abstract   Download Lecture
Expander Graphs -- Constructions and Applications
Thursday, Jan 10, 2008 2:00 PM, MS 6221

Lecture 3 Abstract
Algebraic computation
Friday, Jan 11, 2008 2:00 PM, MS 6627

Background reading:

All available from my website (see survey papers) http://www.math.ias.edu/~avi/BOOKS/index.html

For lecture 1 (and much more), my ICM paper "P, NP and mathematics - a computational complexity perspective"

For lecture 2 (and much more), my Bulletin monograph (with Hoory and Linial): "Expander graphs and their applications".

For lecture 3, short lecture notes: "Arithmetic complexity - a survey" (and the refs therein).