Princeton University Logo
Princeton University
Computer Science Dept.

COS 487/MAT 407
Theory of Computation

Gillat Kol

Fall 2017

Course Summary

What is computation? What can be computed in principle with unbounded computational resources? What can be computed efficiently? What can we gain by formally modeling computation and how do different models relate to one another? How can models highlight different resources of computations, such time, memory, communication, and randomness. We will consider these questions and others using a rigorous mathematical approach. We will discuss what we know as well as some of the central open problems in pure and applied mathematics, and specifically the P vs. NP problem.

Prerequisites: COS 340/341 or equivalent math background (basically, the ability to do mathematical proofs).

About This Course

Text:  Introduction to the Theory of Computation (3rd Edition) by Michael Sipser.

Grading: The grade will be based upon assignments, which will be handed out every roughly two weeks. A week will be given to complete each assignment. Collaborating with your classmates on assignments is encouraged, with the exception of the last assignment that should be completed alone. The last assignment will constitute for 30% of the grade and the rest of the assignments for 70%.
Assignments should be typed. LaTeX is strongly recommended, it's free and can be downloaded here. Here is a suggested LaTaX template for problem sets' solutions (.tex), this is what it looks like once compiled (.pdf).

Administrative Information

Lectures: Tue-Thu 1:30-2:50pm, Room: Friend Center 016, Signup on Piazza: Link

Professor: Gillat Kol - 316 CS Building 
TA: Raghuvansh Saxena 

TA office hours Tuesdays 4:30-6:00pm, CS Building tea room (second floor)  

Honor Code for This Course

The grade is based on problem sets. You are encouraged to work in groups up-to three people on each problem set, accept the last problem set (groups may change between problem sets). However, we ask that you dedicate enough time to think about each problem by yourself before consulting others. You must write up each problem solution by yourself without assistance and are asked to identify your collaborators on problem sets. You must complete the last problem set by yourself and are not allowed to discuss it with anyone until after the deadline.
You may consult your course notes, the text (Sipser), and any resource given in this webpage. The assignment questions may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.

Schedule and Readings

Lecture topics
Lecture 1,
Sep 14
Introduction to Course Topics
- Computational models.
- Computability theory and connections to mathematical logic.
- Complexity theory and the P vs. NP problem.

Topic: Finite Automata
- Deterministic finite automata (DFA): definition, examples.
Chapter 1.1 of text.
Lecture 2,
Sep 19
Topic: Finite Automata (cont'd)
- Nondeterministic finite automata (NFA): definition, equivalence of DFAs and NFAs.
- Regular expressions: definition, examples.
Chapters 1.2-1.3 of text.
Lecture 3,
Sep 21
Topic: Finite Automata (cont'd)
- Regular expressions: equivalence to DFAs.
- Nonregular languages: the pumping lemma.
Chapters 1.3-1.4 of text.
Lecture 4,
Sep 26
Topic: Streaming Algorithms
- Definition.
- The distinguishably technique for space lower bounds.
- The most frequent element problem - space upper and lower bounds.
Notes on streaming algorithms by Ryan Williams and Luca Trevisan's.
Notes on finding the majority element of a stream.
Lecture 5,
Sep 28
Topic: Streaming Algorithms (cont'd)
- The number of distinct elements problem - space upper and lower bounds.
- The randomized streaming model: randomized algorithm for sampling and number of distinct elements.
Notes on streaming algorithms by Ryan Williams and Luca Trevisan.
Lecture 6,
Oct 3
Topic: Turing Machines
- Deterministic Turing machines: definition, examples.
- Multi-tape Turing machine: definition, equivalence to single-tape Turing machines.
Chapters 3.1,3.2 of text.
Lecture 7,
Oct 5
Topic: Turing Machines (cont'd)
- Nondeterministic Turing machines: definition, equivalence to deterministic Turing machines.
- The Church-Turing Thesis.

Topic: Computability Theory
- Definition of decidable and recognizable languages.
Chapters 3.2,3.3,4.1 of text.
Lecture 8,
Oct 10
Topic: Computability Theory (cont'd)
- Examples of decidable and recognizable languages.
- Diagonalization arguments and undecidable languages (Acceptability and Halting).
- Unrecognizable languages.
Chapter 4 of text.
Lecture 9,
Oct 12
Topic: Computability Theory (cont'd)
- Reductions: definition, examples.
Chapters 5.1,5.3 of text.
Lecture 10,
Oct 17
Topic: Computability Theory (cont'd)
- More reductions.
- Rice's theorem.
Chapter 5.1 of text.
Proof of Rice's theorem is the answer to Problem 5.28.
Lecture 11,
Oct 19
Topic: Computability Theory (cont'd)
- Connections to mathematical logic:
  * Proof systems.
  * Gödel's first incompleteness theorem.
Notes on unprovable statements by Luca Trevisan.
Lecture 12,
Oct 24
Topic: Computability Theory (cont'd)
- Connections to mathematical logic:
  * Gödel's second incompleteness theorem.
  * The Church-Turning theorem (checking whether a statement has a proof is undecidable).
- Kolmogorov complexity: definition.
Notes on unprovable statements by Luca Trevisan.
Chapter 6.4 of text.
Lecture 13,
Oct 26
Topic: Computability Theory (cont'd)
- Kolmogorov complexity: undecidability of the compression problem.

Topic: Complexity Theory
- The Extended Church-Turing Thesis.
- Polynomial time algorithms and the P complexity class.
- The time hierarchy theorem.
Notes on Kolmogorov complexity by Luca Trevisan.
Chapters 7.1-7.2,9.1 of text.
Lecture 14,
Nov 7
Topic: Complexity Theory (cont'd)
- The NP complexity class: definition via verifiers, examples.
- The P vs. NP problem.
- Gaining from P ≠ NP: cryptography and derandomization.
Chapter 7.3 of text.
Lecture 15,
Nov 9
Topic: Complexity Theory (cont'd)
- Definition of NP via non-deterministic Turing machines.
- Polynomial time reductions: definition and examples.
Chapters 7.3-7.4 of text.
Lecture 16,
Nov 14
Topic: Complexity Theory (cont'd)
- NP-complete problems: definition.
- Cook-Levin Theorem: 3SAT is NP-complete.
Chapter 7.4 of text.
Lecture 17,
Nov 16
Topic: Complexity Theory (cont'd)
- Cook-Levin Theorem: 3SAT is NP-complete (cont'd).
- NP-complete problems: examples.
Chapters 7.4-7.5 of text.
Lecture 18,
Nov 21
Topic: Complexity Theory (cont'd)
- Ladner's Theorem: infinitely many levels of difficulty in NP (statement only).
- The PSPACE complexity class: definition.
- TQBF is PSPACE-complete.
Chapters 8.2-8.3 of text.
Lecture 19,
Nov 28
Topic: Complexity Theory (cont'd)
- PSPACE and winning strategies in two-players games.
- The coNP complexity class.
Chapter 8.3 of text.
Lecture 20,
Nov 30
Topic: Complexity Theory (cont'd)
- Oracle machines, relativizing proofs.
- Baker-Gill-Solovay Theorem: diagonalization does not suffice to settle the P vs. NP problem.
Chapter 9.2 of text.
Lecture 21,
Dec 5
Topic: Complexity Theory (cont'd)
- Randomized algorithms and the BPP complexity class: definition, examples.
- The P vs BPP problem.
Chapter 10.2 of text.
Lecture 22,
Dec 7
Topic: Complexity Theory (cont'd)
- Interactive proofs: the graph-nonisomorphism example, IP = PSPACE (statement only).
- Zero knowledge: the graph-isomorphism example.
Chapter 10.4 of text.
Arora-Barak book Chapter 8.3.
Lecture 23,
Dec 12
Topic: Complexity Theory (cont'd)
- The PCP theorem (Probabilistically Checkable Proofs).

Topic: Cryptography
- One-time pads.
- One-way functions.
Chapter 10.6 of text.
Arora-Barak book Chapters 18.1 and 10.1.
Lecture 24,
Dec 14
Topic: Cryptography (cont'd)
- Public key encryptions and the Diffie-Hellman Key exchange protocol.
- Cryptographic pseudo-random generators and the Goldreich-Levin Theorem.
Arora-Barak book Chapters 10.2-10.3.

Problem Sets

Problem Set 1. Out: September 20. Due: September 28. (pts:60; mean: 50.6; median: 54; stddev: 10.6)
Problem Set 2. Out: October 4. Due: October 12. (pts:60; mean: 46; median: 49; stddev: 12)
Problem Set 3. Out: October 24. Due: November 9. (pts:60; mean: 52; median: 54; stddev: 6)
Problem Set 4. Out: November 26. Due: December 5. (pts:60; mean: 53; median: 52.5; stddev: 4.5)
Problem Set 5. Out: December 7. Due: December 15. (pts:100; mean: 89.1; median: 94.5; stddev: 11.9)