Topics and Events, Day by Day
The table below will be updated throughout the term.
Any content that's colored light gray is tentative and subject to change.
| Phase 1: Delving deeper into Nondeterminism, Time and Space | |||
| 1 |
Tue Sep 16 | Review of languages and Turing Machines, DTIME, NTIME | [Sip: 3,4,5,7] (notes) |
| 2 |
Thu Sep 18 | Review of NP-completeness and reductions | [Sip: 3,4,5,7] (notes) |
| X |
Fri Sep 19 | Special session: are you ready for this course? | |
| 3 |
Tue Sep 23 | Space complexity; Savitch's Theorem; PSPACE and PSPACE-completeness | [Sip: 8] (notes) |
| 4 |
Thu Sep 25 | Sublinear space (N, NL); Logspace reductions; NL-completeness; Immerman-Szelepcsenyi (NL = coNL) | [Sip: 8] (notes) |
| X |
Fri Sep 26 | Not used | |
| 5 |
Tue Sep 30 | Hierarchy theorems: space and time; Polynomial hierarchy (PH) | [Sip: 9], [AB: 3, 5] |
| 6 |
Thu Oct 02 | Circuits; Non-uniformity; Shannon's Theorem; Karp-Lipton Theorem | [AB: 6] (notes) |
| X |
Fri Oct 03 | Catch up | |
| Phase 2: The Power of Randomness | |||
| 7 |
Tue Oct 07 | Randomization: RP, coRP, BPP; Examples: Primality, PIT; Schwartz-Zippel | [AB: 7] |
| X |
Thu Oct 09 | TBD | |
| 8 |
Fri Oct 10 | More examples: USTCON, Matching; Adleman's Theorem | [AB: 7] |
| 9 |
Tue Oct 14 | Sipser-Gacs Theorem; Randomized reduction; Valiant-Vazirani Theorem | |
| X |
Thu Oct 16 | TBD | |
| 10 |
Fri Oct 17 | Foundations of cryptography; one-way functions, pseudorandom generators | |
| 11 |
Tue Oct 21 | Next-bit unpredictability; Yao's hybrid argument; Goldreich-Levin Theorem | |
| X |
Thu Oct 23 | TBD | |
| 12 |
Fri Oct 24 | Goldreich-Levin Theorem: One-way permutations to PRGs | |
| Phase 3: The Power of Interaction | |||
| 13 |
Tue Oct 28 | Interactive proofs (IP); Arthur-Merlin games (AM); Graph Non-Isomorphism | |
| X |
Thu Oct 30 | TBD | |
| 14 |
Fri Oct 31 | Goldwasser-Sipser Protocol; GNI and NP-completeness | |
| 15 |
Tue Nov 04 | Arithmetization; LFKN Theorem; Shamir's Theorem (IP = PSPACE) | |
| X |
Thu Nov 06 | TBD | |
| 16 |
Fri Nov 07 | Introduction to PCPs; PCP theorem; Applications | |
| 17 |
Tue Nov 11 | PCPs and hardness of approximation | |
| 18 |
Thu Nov 13 | The "Unique Games" Conjecture and applications | |