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.

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.

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