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, some obvious (such as time and memory) and others less so (such as communication and randomness). What is gained by considering natural and social phenomenon as computations and looking at central notions such as proofs, knowledge, learning, games, randomness, entropy and more through the computational lens?
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.
Some specific topics: Finite Automata – Very Simple Models (constant memory), Non-determinism (power of guessing), Learning, communication complexity, Streaming algorithms, Powerful models – Turing Machines, Decidability, Kolmogorov Complexity, Time complexity, P vs. NP, NP-completeness, Other Resources: space, randomness, communication, power, … Crypto, Game Theory, … The Computational Lens.
Prerequisites: CS 103 or 103B.
Current Offering: Fall 2020
Instructor: Omer Reingold, Gates 462, reingold (at stanford dot edu)
Brian Axelrod, baxelrod (at stanford dot edu)
Celia Chen, xinuo (at stanford dot edu)
Tom Knowles. tknowles (at stanford dot edu)
Deon Jordan Richmond, deonrich (at stanford dot edu)
Location and Times:
Tue, 10:30 AM – 11:50 on zoom
Book: Michael Sipser, introduction to the theory of computation (2nd or 3rd edition)
– Extra reading: Boaz Barak, Introduction to Theoretical Computer Science (the approach is different from Sipser, but some parts could augment your understanding). Additional reading below.
Office Hours: See on Piazza
HW assignments (see on Piazza):
Homework will be assigned almost every Tuesday and will be due one week later at the beginning of class. No late submission. We will drop your lowest homework grade.
You may (even encouraged to) collaborate with others, but you must:
1. Try to solve all the problems by yourself first
2. List your collaborators on each problem
3. If you receive a significant idea from somewhere, you must acknowledge that source in your solution.
4. Write your own solutions (important!)
Assignments and submissions through gradescope.com
Best to write in LaTex
Tuesday 9/15: Introduction
Watch videos 0-4.
What are computations? The Computational Lens. Course information and topics. Why Theory? Class Preview. The most fundamental open question of CS: graph coloring ?!? Proof techniques (and an example).
Reading: Chapter 0, Introduction, Sipser
– extra reading: Barak’s chapters 0 and 1
What between Ogres, Onions, Parfait, and good proofs?
- Mathematics and Computation, very interesting book by Avi Wigderson, I highly recommend Chapter 20
- An accessible article I wrote of this book (focusing on the computational lens)
- The Computational Lens plus a talk
- Four talks: lens of computation in the sciences
- Panel Discussion
And if my megalomaniac view of the computational lens is not megalomaniac enough, I suggest reading The Last Question by Isaac Asimov
Thursday 9/17: Quiz (survey)
Tuesday 9/22: Deterministic Finite Automata, Closure Properties, Nondeterminism, equivalence of DFSa and NFAs, regular expression and the languages they correspond to.
Watch videos 5-11
Reading (for next week as well): Chapter 1, Sipser
Thursday 9/24 Quiz
Tuesday 9/29: Non-Regular Languages, The Pumping Lemma, An Algorithm for Minimizing a DFA. The Myhill-Nerode Theorem, Learning DFAs
Watch videos 12-15
Reading: Chapter 1.4, Sipser; A note on DFA minimization and Myhill-Nerode
Thursday 10/1: Quiz
Tuesday 10/6 Streaming Algorithms, Communication Complexity + Begin Turing Machines (deciding vs. recognizing)
Watch videos 16-19
- A note on streaming Algorithms;
- Article on finding frequent elements
- Survey on Communication Complexity
- Turing’s paper.
- Sipser 3
- videos on asymptotic notation (among other preliminaries and relevant videos):
Thursday 10/8: Quiz
Tuesday 10/13: Continue Turing Machines: , Multitape TM, Universal Turing Machines, Nondeterministic Turing Machines, Undecidable and Unrecognizable, A_TM is unrecognizable, Mapping Reductions
Watch videos 20-24
- Sipser 4
Thursday 10/15: Quiz
Tuesday 10/20: Rice’s Theorem, Oracle Machines, Hierarchy of Undecidable Problems, Self Reference, Self Reference, Foundation of Mathematics, Kolmogorov Complexity
Watch videos 25-29
- Sipser 5, 6
- Note on Rice’s Theorem
- Note on Computability and Logic
- Rosencrantz & Guildenstern Are Dead (1990) – Heads Scene
- Note on Kolmogorov Complexity
Thursday 10/22: Quiz
Tuesday 10/27: Time Complexity, P, Time Hierarchy Theorems, NP and Polynomial-Time (Mapping) Reductions
Watch videos 30-33
- Sipser 7-7.3, 9.1
- Note on NP-Completeness
Thursday 10/29 : Quiz
Tuesday 11/3: NP-Completeness, Cook-Levin Theorem, More NP-Completeness through Poly-Time Reductions, coNP, Oracles, Polynomial Hierarchy
Watch videos 34-36
Thursday 11/5: Quiz
Tuesday 11/10: Space Complexity, advanced topics on proofs (PCPs, Hardness of Approximation, IPs, Zero-Knowledge)
Watch videos 37-39
- Finish Sipser 7, Sipser 8.2, 9.1, 9.2
Thursday 11/12: Quiz
Advanced (not required) reading:
Tuesday 11/17: Course Wrap-Up, Computational Lens, Randomness and Pseudorandomness, Algorithmic Fairness
Watch videos 40-42
Advanced (not required) reading:
- Arora-Barak Chapters 7, 16
Thursday 11/19: Quiz