Theory of Computation - 32366 - CS 7805

Instructor:  Emanuele Viola
Meetings: Monday and Wednesday, 2:50 pm - 4:30 pm, Shillman Hall 105.
Makeup class time is 2:50 - 4:30, location 164 West Village H.
Office Hours: After class in classroom and then in 246 West Village H.

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 (discussed in the project section).

Your grade is 50% homework and 50% project.

Scroll down to project discussion and homework policy.

Class schedule

Jan 10.
Administrivia. Overview of the class and papers for the project.

Jan 12.
Class canceled due to the "snowstorm."

Jan 17.
Martin Luther King Jr.'s Birthday observed, no classes.

Jan 19.
Writing mathematical proofs. [S; 0], [V; 1-4]

Jan 21. Makeup day: we meet in 164 West Village H.
Writing mathematical proofs. [AB; 0.3], [S; 0], [V; 1-4]

Jan 24.
Writing mathematical proofs. [S; 0], [V; 1-4]

Jan 26.
Regular sets. [S; pp. 64,65; 78-82 (just lemma statement and examples)]. [V; 5]. Induction [V; 6]. [HMW 1.4.2, 1.4.3] (handed out in class)
Homework 1 assigned:
(1) [V exercise 2].
(2) [V exercise 3].
(3) Prove that { x | x = wtw for some w and t belonging to {0,1}({0,1}*) } is not regular (this is [S problem 1.46 d]).
(4) Prove or disprove the claim: There exists a function f(n) = ω(n) such that {1f(n) | n > 0 is an integer} is regular.

Jan 31.
Induction. Counting. [V; 6, 7].

Feb 2.
Counting. The probabilistic method. [V; 7, 8].
Homework 1 due before class.

Feb 7.
The probabilistic method. [V; 8].
Homework 2 assigned:
(1) [V exercise 6] (Ramsey theory).
(2) [V exercise 8] (3-cliques).
(3) [V exercise 9] (Non-regular sets without pumping lemma).

Feb 9. The probabilistic method. [V; 8].

Feb 14.
Models of computation: Turing machines. [S 137-149, 247-253]

Feb 16.
Homework 2 due before class.
Models of computation: Random-access Turing machines, RAM machines [hand out sent via email]

Feb 18.
Makeup day: we meet in 164 WVH
3SUM hardness [hand out sent via email, and paper ``On a class of O(n^2) problems in computational geometry'' below]

Feb 21.
President's day. No classes.

Feb 23.
P, NP. [Sipser 7]
Homework 3 assigned:
(1) [V exercise 14] (Even number of heads).
(2) Consider the language L = {0n | n is a power of 2}.
Show that L is in TIME(O(n log n)) on single-tape Turing machines.
Then show that L is in TIME(O(n)) on two-tape Turing machines.
(3) [Sipser 7.32] Show the NP-completeness of {(M,x,#t) | Turing Machine M accepts input x within t steps on at least one branch. (Note the symbol # is repeated t times.)
(4) [Sipser 7.34] A subset of the nodes of a graph G is a dominating set if every other node of G is adjacent to some node in the subset. By a giving a reduction from VERTEX-COVER, show the NP-completeness of DOMINATING SET = {(G,k) | G has a dominating set with k nodes}.

Spring break.

Mar 7.
3SAT is NP-complete.
[Sipser 276-283]

Mar 9. No class, Emanuele's away.

Mar 14.
Additional NP-complete problems.
[Sipser 7.5]
Homework 3 due before class.

Mar 16.
Randomized computation [AB 7]. The Time Hierarchy Theorem [AB 3.1].

Mar 21. No class, Emanuele's away.

Mar 23. No class, Emanuele's away.

Mar 28.
Space complexity [Sipser 8]

Mar 30.
Space complexity [Sipser 8]

Apr 4. The polynomial-time hierarchy, time-space tradeoffs for SAT, and circuit lower bounds.

Apr 6. Chosen by the students: Undirected connectivity in logarithmic space [Notes]

Apr 11.
Project presentations: Paul & Vincent: Equivalence of Models of Computation for Nearly Linear Time.

Apr 13.
Project presentations: Jose & Mitesh. An Introduction to Probabilistically Checkable Proofs and the PCP Theorem.

Apr 18. Patriot's day, no classes.

Apr 20.
Project presentations: Peter & Travis. On 3-SUM hardness.

Apr 25.
Final exams week.
Project presentations: Bahar & Maziar. Subcubic Equivalence of Triangle Detection and Matrix Multiplication.


Your project should be based on one (or more) research papers. **You are asked to extract some interesting claim from the paper(s), and prepare a write-up and a presentation of it that a non-expert can understand.** You do not have to cover all of the results in the paper. I expect most presentations will only cover a fraction of a paper.
You will work in pairs. Each pair will take a whole lecture. Each member of the pair will present for roughly half of it but must be able to answer questions about all of the work. Your write-up must include a proof, and your presentation must include at least a proof sketch giving all the main ideas.
Stop by during office hours to discuss potential projects in detail.

Timeline: You must signal your preferences by February 23rd. Do try to signal more than one: since most likely you'll work in pairs, you may have to compromise. If you have a preference for a partner, let me know and I'll take that into account.
Then, during office hours before your presentation, you should come see me with a draft of your write-up. I will expect to see that you have identified a claim to write about and to present.

Below are some suggested papers for projects. You are free to suggest your own.

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
Hennie-Stearns, Pippenger-Fischer simulation. See here, here , and Chapter 1.
Nearly linear time
Oblivious RAMs without Cryptographic Assumptions

Homework policy

To achieve Goal (1) at the top of this page, I will expect your solutions to be *polished*. Strive to give effective, compact solutions. Your solutions should touch on all the main points, but long calculations or discussions are not required nor sought. Make solutions that can be framed as they are.

Except for office hours, for the homework you must work on your own.

Problems sets are due at the beginning of class. Late submissions are never accepted.

Please type (not hand-write) your submission and submit them on paper (not file). Typing your solutions is beneficial because it forces you to think twice about what you write.

To hand them in: give it to me or slide them under my door West Village H (246).

Unless specified otherwise, in your solutions you can use the following and only the following: what proved in class, and any basic fact you were supposed to know before taking this class. Anything else you must prove.