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