**
Theory Reading Group**

**Summer 2005 Schedule**

Date | Information |

ThursdayAugust 25 2005 |
Topic: Min-wise perumatutionsEric Skaug will lead the discussion. 1:00pm, 4397 CS. |

ThursdayAugust 18 2005 |
Topic:
Irit Dinur's proof of the PCP Theorem3:30pm, 4397 CS. |

ThursdayAugust 4 2005 |
Topic: Metric Embeddings (Including
Bourgain's Theorem)Eric Skaug will lead the discussion. 1:00pm, 4397 CS. |

ThursdayJuly 14 2005 |
Topic: Random walks and circuit resistance.Michael Kowalczyk will lead the discussion. 1:00pm, 4397 CS. |

ThursdayJune 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. |

WednesdayJune 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. |

FridayJune 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. |

ThursdayMay 26 2005 |
Topic: If P!=NP, there are
NP-intermediate problems.Reference: Ladner's theorem. 1:00-2:00, 4397 CS. |