Theory of Computation - 32081 - CS 7805

Instructor: Emanuele Viola
Meetings: Monday 2:50 pm - 4:30 pm, Thursday 8:45 - 10:25 a.m. 106 YMCA (316 Huntington Ave)
Office hours.

This course has three goals:
(1) To strengthen your analytical skills/mathematical maturity/expository skills, especially by teaching you how to write mathematical proofs.
(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 project.

The syllabus is divided in three corresponding parts.

We will be using the following:
[AB] Computational Complexity Theory by Arora and Barak,
[HMU] Introduction to Automata Theory, Languages, and Computation, 3rd Edition, by Hopcroft, Motwani, Ullman,
[S] Introduction to the Theory of Computation , 2nd edition, by Sipser,
[V] 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 this.

Hennie-Stearns, Pippenger-Fischer simulation. See here, here , and Chapter 1. Original papers: here and here.

Short propositional formulas represent nondeterministic computations, by Stephen A. Cook. Published in: Information Processing Letters, Volume 26 Issue 5, Jan. 11, 1988.

Other papers

On a class of O(n^2) problems in computational geometry
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
Finding, Minimizing, and Counting Weighted Subgraphs
Towards polynomial lower bounds for dynamic problems
On the possibility of faster SAT algorithms
Complexity of k-sat(builds on next one)
Which problems have strongly exponential complexity?
Computational complexity and informational asymmetry in financial products
Oblivious RAMs without Cryptographic Assumptions