Theory Reading Group

Summer 2005 Schedule

Date Information
Thursday
August 25 2005		 Topic: Min-wise perumatutions
Eric Skaug will lead the discussion.
1:00pm, 4397 CS.
Thursday
August 18 2005		 Topic: Irit Dinur's proof of the PCP Theorem
3:30pm, 4397 CS.
Thursday
August 4 2005		 Topic: Metric Embeddings (Including Bourgain's Theorem)
Eric Skaug will lead the discussion.
1:00pm, 4397 CS.
Thursday
July 14 2005		 Topic: Random walks and circuit resistance.
Michael Kowalczyk will lead the discussion.
1:00pm, 4397 CS.
Thursday
June 30 2005		 Paper presentation: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines by Scott Diehl and Dieter van Melkebeek.
Scott will present his recent research.
4:00pm, 3331 CS.
Wednesday
June 8 2005		 Topic: average case complexity.
References: notes on Levin's Theory of Average-Case Complexity, A Personal View of Average-Case Complexity, On the Theory of Average Case Complexity.
Jeff will lead the discussion.
1:00-2:30, 4397 CS.
Friday
June 3 2005		 Topic: time hierarchies for semantic classes.
Reference: Time Hierarchies for Computations with a Bit of Advice by Konstantin Pervyshev.
Bess will lead the discussion.
12:00-1:30, 4397 CS.
Thursday
May 26 2005		 Topic: If P!=NP, there are NP-intermediate problems.
Reference: Ladner's theorem.
1:00-2:00, 4397 CS.