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 2019**

**Instructor**: Omer Reingold, Gates 462, reingold (at stanford dot edu)

**CAs**:

Andrew (Andy) Chen, asjchen (at stanford dot edu)

William Marshall, wfm (at stanford dot edu)

Hubert Teo, hteo (at stanford dot edu)

Anastasiya Vitko, avitko (at stanford dot edu)

**Location and Times**:

Tue, Thu 10:30 AM – 11:50 AM at Gates B3

*Video cameras located in the back of the room will capture the instructor presentations in this course. For your convenience, you can access these recordings by logging into the course Canvas site. These recordings might be reused in other Stanford courses, viewed by other Stanford students, faculty, or staff, or used for other education and research purposes. Note that while the* *cameras are positioned with the intention of recording only the instructor, occasionally a part of your image or voice might be incidentally captured. If you have questions, please contact a member of the teaching team.*

**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)

**Office Hours**: See on Piazza

**HW assignments (see on Piazza)**:

Homework will be assigned every Tuesday (except for the week before the midterm) 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

**Grades: **Will be at least a combination of 45% HW assignments, 25% midterm, 30% finals

**Lectures (content for future dates is tentative)**:

**Tuesday 9/24**: **Introduction**

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 Lecture 0 and 1

**Additional**:

What between Ogres, Onions, Parfait, and good proofs?

- Mathematics and Computation, very interesting book by Avi Wigderson, I highly recommend Chapter 20
- 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/26**: Deterministic Finite Automata, Closure Properties, Nondeterminism

Reading (for next few classes): Chapter 1, Sipser

**Tuesday 10/1**: Finish closure properties of regular languages, Show equivalence of DFSa and NFAs, define regular expression and characterize the languages they correspond to.

**Thursday 10/3**: Non-Regular Languages, The Pumping Lemma, An Algorithm for Minimizing a DFA

PPTX, PDF (to be finished next class)

Reading: Chapter 1.4, Sipser; A note on DFA minimization and Myhill-Nerode

**Tuesday 10/8**: Finish Minimizing DFA, The Myhill-Nerode Theorem

PPTX, PDF (to be finished next class)

**Thursday 10/10**: Learning DFAs, Streaming Algorithms

No new slides

- Angluin’s classic paper on learning DFAs
- A note on streaming Algorithms;
- Article on finding frequent elements

**Tuesday 10/15**: Communication Complexity + Begin Turing Machines: deciding vs. recognizing

PPTX, PDF (to be completed next week)

- Survey on Communication Complexity
- Turing’s paper, and here
- Sipser 3

**Thursday 10/17**: Continue Turing Machines: deciding vs. recognizing, Multitape TM, Universal Turing Machines, Nondeterministic Turing Machines, Undecidable and Unrecognizable

PPTX, PDF (to be completed next week)

**Tuesday 10/22**: A_TM is unrecognizable, Mapping Reductions

(no new slides)

**Thursday 10/24**:

Rice’s Theorem, Oracle Machines, Hierarchy of Undecidable Problems, Self Reference

- Sipser 4, 5, 5.3
- Note on Rice’s Theorem

**Tuesday 10/29**: in-class midterm

**Thursday 10/31**: Self Reference, Foundation of Mathematics, Kolmogorov Complexity

PPTX, PDF (continue next class)

**Tuesday 11/5**: Finish Kolmogorov Complexity, Time Complexity, P

- Sipser 7 for the next few weeks, 9.1

**Thursday 11/7**: Finish Time Hierarchy Theorems, NP and Polynomial-Time (Mapping) Reductions

**Tuesday 11/12**: NP-Completeness, Cook-Levin Theorem

PPTX, PDF

- Note on NP-Completeness

**Thursday 11/14**: Cook-Levin Theorem

PPTX, PDF

**Tuesday 11/19**:

More NP-Completeness through Poly-Time Reductions

PPTX, PDF

**Thursday 11/21**: coNP, Oracles, Polynomial Hierarchy, Space Complexity

**Tuesday 11/26**: Thanksgiving – no class

**Thursday 11/28**: Thanksgiving – no class

PPTX, PDF

- Finish Sipser 7, Sipser 8.2 and 9.2

**Tuesday 12/3**: Approximation and Hardness, PCPs, IPs, Zero-Knowledge + Wrap Up

PPTX, PDF

Additional (not required) reading:

- Arora-Barak Chapters 8 and 18
- Where is Waldo (Applied Kid Cryptography)

**Thursday 12/5**: “Ask Me Anything”

**Thursday, December 12**, 3:30-6:30 p.m: **Finals**