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.
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
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.