CS7805: Theory of Computation


[Home] [Schedule]
The schedule is tentative and based on the 2018 offering of the course. It is subject to change (e.g. snow days)
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