Theory of Computation - 32081 - CS 7805
Meetings: Monday 2:50 pm -
4:30 pm, Thursday 8:45 - 10:25 a.m. 106 YMCA (316 Huntington Ave)
This course has three goals:
(1) To strengthen your
analytical skills/mathematical maturity/expository
skills, especially by teaching you how to write
(2) To teach you fundamental concepts of Theory of
Computation, such as models of computation, running time, and NP-completeness.
(3) To expose you to current research in Theory of
Computation by having you work on a paper
The syllabus is divided in three corresponding parts.
We will be using the following:
Computational Complexity Theory by Arora and Barak,
Introduction to Automata Theory, Languages, and Computation, 3rd Edition, by Hopcroft, Motwani, Ullman,
Introduction to the Theory of Computation , 2nd edition, by Sipser,
Think like the pros, a preliminary set of notes by Viola.
For Part (1) we will use [HMU], [S], and [V].
For Part (2) we will use [AB], [HMU], and [S].
For Part (3) we will work with
research papers .
Your grade is based on your presentations and your write-ups.
[V] 2, 3, 5, 6, 8, 9, this proof of the Chernoff Bound, 12, 13.
If we cover the pumping lemma and regular sets, feel free to propose the related exercises in [V].
Feel also free to propose exercises on Ramsey Theory, the probabilistic method, or other material in combinatorics.
Papers for group project:
Nearly linear time. Builds on
Hennie-Stearns, Pippenger-Fischer simulation. See here,
Short propositional formulas represent nondeterministic computations, by Stephen A. Cook. Published in:
Information Processing Letters,
Volume 26 Issue 5, Jan. 11, 1988.
On a class of O(n^2) problems in computational geometry
Equivalences Between Path, Matrix, and Triangle
Minimizing, and Counting Weighted Subgraphs
lower bounds for dynamic problems
possibility of faster SAT algorithms
k-sat(builds on next one)
problems have strongly exponential complexity?
Computational complexity and informational asymmetry in financial products
Oblivious RAMs without Cryptographic Assumptions