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] |
| 8 |
Thu Oct 09 | Theorems of Adleman and Sipser-Gacs; RL, BPL, NC, RNC: USTCON and MATCH | [AB: 7] |
| X |
Fri Oct 10 | Not used | |
| 9 |
Tue Oct 14 | Randomized reductions: Valiant-Vazirani Theorem | [AB: 7, 17] |
| 10 |
Thu Oct 16 | Foundations of cryptography; one-way functions, pseudorandom generators | [AB: 9] |
| X |
Fri Oct 17 | Not used | |
| 11 |
Tue Oct 21 | Unpredictability and PRGs; Yao's hybrid argument; Goldreich-Levin Theorem | [AB: 9] |
| 12 |
Thu Oct 23 | One-way permutations to PRGs; Applications: telephone poker, encryption | [AB: 9] (notes) |
| X |
Fri Oct 24 | Not used | |
| Phase 3: The Power of Interaction | |||
| 13 |
Tue Oct 28 | Interactive proofs (IP); Arthur-Merlin games (AM, MA); Graph Non-Isomorphism | [AB: 8] |
| 14 |
Thu Oct 30 | Goldwasser-Sipser Protocol; GNI and NP-completeness | [AB: 8] (notes) |
| 15 |
Fri Oct 31 | Zero-knowledge proofs | [AB: 9.4] |
| 16 |
Tue Nov 04 | Arithmetization; LFKN Theorem; Shamir's Theorem (IP = PSPACE) | [Sip: 10.4] |
| 17 |
Thu Nov 06 | Introduction to PCPs; PCP theorem; Applications | [AB: 11] |
| X |
Fri Nov 07 | TBD | |
| 18 |
Tue Nov 11 | PCPs and hardness of approximation | |
| 19 |
Thu Nov 13 | The "Unique Games" Conjecture and applications | |
| X |
Fri Nov 14 | TBD | |
| 20 |
Tue Nov 18 | Wrap-up | |