Tuesday and Thursday, 5:30-7:00 PM, Bryan 509C.

Office Hours: Wednesday 5-6 PM, Bryan 522

Email:

Monday | Tuesday | Wednesday | Thursday | Friday |

Aug 25 |
Aug 26 L1: Modeling Computation AB 1.1-1.3;1.6 |
Aug 27 |
Aug 28 L2: Basic Complexity Theory AB 1.4, 1.5, 3.1, 4.1 Assigned: Homework 1 |
Aug 29 |

Sept 01 Holiday |
Sept 02 L3: Basic Circuit Complexity AB 6.1-6.3, 6.5, 6.6 |
Sept 03 |
Sept 04 L4: Nonuniform Complexity finish AB 6.1-6.3; 14.4.4 Due: Homework 1 Assigned: Homework 2 |
Sept 05 |

Sept 08 |
Sept 09 L5: Barrington's Theorem; Circuit Depth Jukna 15.1, 15.4; AB 6.7.1 |
Sept 10 |
Sept 11 L6: Circuit Lower Bounds I: random restrictions Jukna 12.3 (AB 14.1) |
Sept 12 |

Sept 15 |
Sept 16 L7: Circuit Lower Bounds II: switching lemma, polynomial approximations AB 14.1.2, start 14.2 |
Sept 17 |
Sept 18 L8: Circuit Lower Bounds III: Razborov-Smolensky, ACC _{0} and TC_{0}finish AB 14.2 (Jukna 12.5-12.6, p.346) Due: Homework 2 Assigned: Homework 3 |
Sept 19 |

Sept 22 |
Sept 23 L9: Randomized Complexity AB 7.1, 7.2.3, 7.3, 7.4.1, 7.5.1, 20.1 |
Sept 24 |
Sept 25 L10: Pseudorandom Generators AB 20.1.1, 21.6 |
Sept 26 |

Sept 29 |
Sept 30 L11: Hardness vs. Randomness AB 9.3.1, 20.1.2, 20.2, intro. of 19.4 |
Oct 01 |
Oct 02 L12: Application: Cryptography AB 9.1, 9.2.1-9.2.3, 9.5.1 Due: Homework 3 Assigned: Homework 4 |
Oct 03 |

Oct 06 |
Oct 07 L13: Reductions and Completeness AB 2.2, 4.3, 6.7.2 |
Oct 08 |
Oct 09 L14: NP AB 2.1, 2.3 (6.1.2), 2.7.1-2.7.3, 2.7.5 |
Oct 10 |

Oct 13 |
Oct 14 L15: Ubiquity of NP-completeness AB 2.4, 3.3 |
Oct 15 |
Oct 16 L16: Nondeterministic Space AB 2.1.2, 4.2.1 (start 4.2), 4.3 Due: Homework 4 Assigned: Homework 5 |
Oct 17
Holiday |

Oct 20 |
Oct 21 L17: Co-Nondeterminism AB 2.6.1, 4.2, start 4.3.2 |
Oct 22 |
Oct 23 L18: Immerman-Szelepcsenyi; Alternation I AB 4.3.2, 5.1, 5.3, start 5.2 |
Oct 24 |

Oct 27 |
Oct 28 L19: Alternation II; Relativization Barrier AB 5.2.1, 5.2.2, 5.5, 3.4 |
Oct 29 |
Oct 30 L20: Natural Proofs Barrier finish AB 3.4, AB 6.4, 23.1, 23.2-23.2.1 Due: Homework 5 Assigned: Homework 6 |
Oct 31 |

Nov 03 |
Nov 04 L21: Counting and Sampling AB 23.2.2-23.2.3, 23.3, 17.1, 17.2, 17.3 |
Nov 05 |
Nov 06 L22: Toda's Theorem AB 17.3.2, 17.4 |
Nov 07 |

Nov 10 |
Nov 11 L23: Interaction finish AB 17.4.4, AB 8.1, 8.2-8.2.2 |
Nov 12 |
Nov 13 L24: IP = PSPACE AB 8.2.4 (+7.5.2), 8.3-8.3.2 Due: Homework 6 |
Nov 14 |

Nov 17 |
Nov 18 L25: PCP I AB 8.3.3, 8.5, 11.1, 11.2, 11.4 |
Nov 19 |
Nov 20 L26: PCP II AB 11.3, 11.5 |
Nov 21 |

Nov 24 |
Nov 25 Thanksgiving travel day |
Nov 26 |
Nov 27 Thanksgiving |
Nov 28 |

Dec 01 |
Dec 02 L27: PCP III AB 22.1, 22.2 |
Dec 03 |
Dec 04 Final Project Presentations Due: Final Project Write-up |
Dec 05 |