| Date | Topic | Reading |
|---|---|---|
| Jan 7 | Intro, math background, finite automata |
Sipser 1-44 |
| Jan 10 | Non-determinism, closure, regular expression |
Sipser 44-66 |
| Jan 14 |
Equivalence of regex and DFA, pumping lemma |
Sipser 66-82 |
| Jan 17 |
Two-way DFA and equivalence |
www.cs.cornell.edu/courses/cs682/2008sp/Handouts/2DFA.pdf |
| Jan 21 |
Context-free languages |
Sipser 101-111 |
| Jan 24 |
Pushdown automata |
Sipser 111-127 |
| Jan 28 |
pumping lemma, exercises |
Sipser 128-131 |
| Jan 31 |
Church-Turing thesis
|
Sipser 165-170, 182-187, 201-207 |
| Feb 4 |
Decidability |
|
| Feb 7 |
Undecidability and reductions |
|
| Feb 11 |
Undecidability in logic, Gödel's incompleteness |
|
| Feb 14 |
Kolmogorov complexity, P, NP |
Sisper 261-269, 275-284 |
| Feb 18 |
NP-completeness, reductions |
Sipser 285-304 |
| Feb 21 |
No class, Huy at ICPC NA final |
|
| Feb 25 |
Cook-Levin theorem |
Sipser 304-310, 379-387 |
| Feb 28 |
Time hierarchy, non-deterministic time hierarchy, oracle separation |
Arora-Barak 3.1, 3.2, 3.4 |
| Mar 10 |
Space complexity, PSPACE, L, NL, Savitch's theorem |
Arora-Barak 4.1, 4.2 |
| Mar 13 |
Polynomial hierarchy, time-space tradeoff for SAT |
Arora-Barak 5.1-5.4 |
| Mar 17 |
No class, school closed |
|
| Mar 20 |
Circuits, Karp-Lipton |
Arora-Barak 6.1-6.4 |
| Mar 24 |
Randomized computation |
Arora-Barak 7.1-7.4, 7.6, 7.7 |
| Mar 27 |
Counting, #P, Valiant-Vazirani |
Arora-Barak 17.1, 17.2, 17.4.1 |
| Mar 31 |
Interactive proofs, IP, AM, MA |
Arora-Barak 8.1,8.2 |
| Apr 3 |
IP=PSPACE |
Arora-Barak 8.3, 8.4 |
| Apr 7 |
Artem and Max presenting quantum computation |
|
| Apr 10 |
Cryptography |
|
| Apr 14 |
Communication complexity |
|
| Apr 17 |
Hardness amplification |