Princeton
University

COS 487/MAT 407


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).
Lectures: TueThu 1:302:50pm, Room: Friend Center 016, Signup on Piazza: Link
Professor: Gillat Kol
 316 CS Building gkol@princeton.edu
TA: Raghuvansh Saxena rrsaxena@princeton.edu
Honor Code for This Course
The grade is based on problem sets. You are encouraged to work in groups upto 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.Date 
Lecture topics 
Reading 
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.  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.21.3 of text. 
Lecture 3, Sep 21 
Topic: Finite Automata (cont'd)  Regular expressions: equivalence to DFAs.  Nonregular languages: the pumping lemma. 
Chapters 1.31.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.  Multitape Turing machine: definition, equivalence to singletape 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 ChurchTuring Thesis.  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 ChurchTurning 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.  The Extended ChurchTuring Thesis.  Polynomial time algorithms and the P complexity class.  The time hierarchy theorem. 
Notes on Kolmogorov complexity by Luca Trevisan. Chapters 7.17.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 nondeterministic Turing machines.  Polynomial time reductions: definition and examples. 
Chapters 7.37.4 of text. 
Lecture 16, Nov 14 
Topic: Complexity Theory (cont'd)  NPcomplete problems: definition.  CookLevin Theorem: 3SAT is NPcomplete. 
Chapter 7.4 of text. 
Lecture 17, Nov 16 
Topic: Complexity Theory (cont'd)  CookLevin Theorem: 3SAT is NPcomplete (cont'd).  NPcomplete problems: examples. 
Chapters 7.47.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 PSPACEcomplete. 
Chapters 8.28.3 of text. 
Lecture 19, Nov 28 
Topic: Complexity Theory (cont'd)  PSPACE and winning strategies in twoplayers games.  The coNP complexity class.  PSPACE = NPSPACE = coNPSPACE. 
Chapter 8.3 of text. 
Lecture 20, Nov 30 
Topic: Complexity Theory (cont'd)  Oracle machines, relativizing proofs.  BakerGillSolovay 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 graphnonisomorphism example, IP = PSPACE (statement only).  Zero knowledge: the graphisomorphism example. 
Chapter 10.4 of text. AroraBarak book Chapter 8.3. 
Lecture 23, Dec 12 
Topic: Complexity Theory (cont'd)  The PCP theorem (Probabilistically Checkable Proofs). Topic: Cryptography  Onetime pads.  Oneway functions.  Public key encryptions.  Cryptographic pseudorandom generators. 
Chapter 10.6 of text. AroraBarak book Chapters 18.1 and 10.110.3. 