| Date | Topic | Presented by | |
|---|---|---|---|
| Sep. 28, 2005 Sep. 21, 2005 | SL=L | Paul | |
| Sep. 7, 2005 | Tight lower bounds for metric embeddings via expanders | Periklis | |
| July 6, 2005 | Hardness of clique | Ali | * |
| June 29, 2005 | Uniform constructions II: Zig-Zag | Paul | |
| June 15, 2005 | Uniform constructions I: Basic constructions for expanders | Matei | |
| June 8 | Random walks on expanders | Phuong | |
| May 26 | The Computational Complexity of Logical Theories | Charles Rackoff | |
| May 11, 2005 | Attempts to show NL not equal to P | Stephen Cook | |
| April 20, 2005 | Connections between the spectral gap and the expansion factor | Mark | |
| April 13, 2005 | Head-Start (Linear Algebra prerequisites) | Mark | * |