**
Theory Reading Group**

**Fall 2005 Schedule**

Date | Information |

MondayDecember 12, 2005 |
Topic: Quantum computing.Links: TBD.Presenter: Bess Berg.3:30 pm, 4331 CS. |

MondayDecember 5, 2005 |
Topic: Pseudorandom Generators.Links:
Derandomizing BPP and Pseudorandomness - A Survey by Wigderson and
Dinur, Derandomization: A Brief Overview by Kabanets. Presenter: Jeff Kinne.3:30 pm, 4331 CS. |

MondayNovember 21, 2005 |
Topic: Division/Iterated multiplication with small depth circuits.Links:
Division in logspace-uniform NC1 by Andrew Chiu et
al.Presenter: Eric Skaug.3:30 pm, 4331 CS. |

MondayNovember 14, 2005 |
Topic: Time-space lower bounds for SAT.Links:
Time-Space Lower Bounds for Satisfiability by Fortnow et
al.,Better Time-Space Lower bounds for SAT and Related problems by Williams, Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines by Diehl, van Melkebeek. Presenter: Scott Diehl.3:30 pm, 4331 CS. |

MondayNovember 7, 2005 |
Topic: BPtime hierarchy results and discussion.Presenter: Jeff Kinne.3:30 pm, 4331 CS. |

MondayOctober 31, 2005 |
Topic: Sum-product estimate for subsets of a finite field.Links:A Sum-Product
Estimate in Finite Fields, and Applications by Bourgain et al.A sum-product estimate in fields of prime order by Konyagin. Presenter: Anand Sinha.3:30 pm, 4331 CS. |

MondayOctober 24, 2005 |
Student Summer RA talks - no meeting.Vinay and Anand will be giving their "Summer RA" talks at 4pm in 1221 CS. |

MondayOctober 17, 2005 |
Topic: Is P vs NP Formally Independent?Links: Is P Versus NP Formally Independent by Scott Aaronson. Jurgen Van Gael will present. 3:30pm, 4331 CS. |

MondayOctober 10, 2005 |
Topic: Time Hierarchy for BPP with advice.Links: A Generic Time Hierarchy for Semantic Models with One Bit of Advice by Melkebeek and Pervyshev. Jeff Kinne will present. 3:30pm, 4331 CS. |

MondayOctober 3, 2005 |
Topic: Approximating Unique Games.Links: Approximation ALgorithms for Unique Games by Luca Trevisan. Anand Sinha will present. 3:30pm, 4331 CS. |

MondaySeptember 26, 2005 |
Topic: discuss Qual problems.3:30pm, 4331 CS. |

MondaySeptember 19, 2005 |
Topic: Hierarchy Theorems.Links:
Jin-Yi Cai's complexity notes,
Lecture on Nondeterministic Time Hierarchy,
Time Hierarchy for Semantic Models (e.g. BPP) with 1 bit of advice3:30pm, 4331 CS. |

MondaySeptember 12, 2005 |
Topic: Review of Complexity classes.Links:
Jin-Yi Cai's complexity notes,
The Complexity Zoo
A Complexity Map.3:30pm, 4310 CS. |