CS 154: Introduction to the Theory of Computation

 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 2022 – Under Construction 

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


Callum Jan Burgess, callumb (at stanford dot edu)
Christie Di, zidi (at stanford dot edu)
Felipe Correa Dias Godoy, fgodoy (at stanford dot edu)
Saumya Goyal, saumg (at stanford dot edu)
Arthur Lee, arthurlh (at stanford dot edu)

Location and Times:

Tue and Thursday, 10:30 AM – 11:50 PM at TBD.  

The class is flipped. Pre-recorded lectures on YouTube (unfortunately contains ads) and Canvas. Also see Grid of Welcome, curtesy of Logan Matthew Bell and Ricardo Iglesias. A related and multi-instotutes project is here (could be a useful resource). 

The Tuesday meetings will be devoted to Q&A as well as additional examples and will be posted on Canvas only. The Thursday meetings will mostly serve as OHs, not recorded (and not mandatory). In addition, Thursdays will be used for midterms and make-up classes.

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

Lectures (future schedule is tentative)

Tuesday 9/27: Introduction

Assignment: Watch videos 1,2,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?

And if my megalomaniac view of the computational lens is not megalomaniac enough, I suggest reading The Last Question by Isaac Asimov

Tuesday 10/4: Deterministic Finite Automata, Closure Properties, Nondeterminism, equivalence of DFSa and NFAs, regular expression and the languages they correspond to.

Assignments: Watch videos 5-11; PSet 1 published

PPTX: 5p-DFA-overview 6p-DFAs 7p-DFAclosure1 8p-NFAs 9p-NFA2DFA 10p-Closure2 11p-RegExp

PDFs: 5p-DFA-overview 6p-DFAs 7p-DFAclosure1 8p-NFAs 9p-NFA2DFA 10p-Closure2 11p-RegExp

Reading (for next week as well): Chapter 1, Sipser

Tuesday 10/11: Non-Regular Languages, The Pumping Lemma, An Algorithm for Minimizing a DFA. The Myhill-Nerode Theorem, Learning DFAs

Assignments: Watch videos 12-15; PSet 2 published; PSet 1 submitted

PPTX: 12p-pumping 13p-minimizingDFA 14p-Myhill-Nerode 15p-Learning-DFA 

PDF: 12p-pumping 13p-minimizingDFA 14p-Myhill-Nerode 15p-Learning-DFA 

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


Tuesday 10/18 Streaming Algorithms, Communication Complexity + Begin Turing Machines (deciding vs. recognizing)

Assignments: Watch videos 16-19; PSet 3 published; PSet 2 submitted

PPTX: 16p-streaming 17p-Communication-Complexity 18p-TM-overview  19p-TMs

PDF: 16p-streaming 17p-Communication-Complexity 18p-TM-overview 19p-TMs

Tuesday 10/25: Continue Turing Machines: , Multitape TM, Universal Turing Machines, Nondeterministic Turing Machines, Undecidable and Unrecognizable, A_TM is unrecognizable, Mapping Reductions

Assignments: Watch videos 20-24; PSet 4 published; PSet 3 submitted

PPTX: 20p-TM-variants 21p-Universal-TM 22p-counting-argument 23p-concrete-undecidable 24p-mapping-reductions

PDF: 20p-TM-variants 21p-Universal-TM 22p-counting-argument 23p-concrete-undecidable 24p-mapping-reductions

  • Sipser 4

Tuesday 11/1: Rice’s Theorem, Oracle Machines, Hierarchy of Undecidable Problems, Self Reference, Self Reference, Foundation of Mathematics, Kolmogorov Complexity

Assignments: Watch videos 25-29; PSet 5 published; PSet 4 submitted

PPTX: 25p-rices-theorem 26p-oracle-reductions 27p-self-reference 28p-logic 29p-Kolmogorov-Complexity

PDF: 25p-rices-theorem 26p-oracle-reductions 27p-self-reference 28p-logic 29p-Kolmogorov-Complexity

  • 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 11/3: midterm

Tuesday 11/8: democracy day Time Complexity, P, Time Hierarchy Theorems, NP and Polynomial-Time (Mapping) Reductions 

Assignments: Watch videos 30-33; 

PPTX: 30p-Complexity-overview 31p-time-complexity 32p-NP 33p-poly-time-reductions

PDF: 30p-Complexity-overview 31p-time-complexity 32p-NP 33p-poly-time-reductions

  • Sipser 7-7.3, 9.1
  • Note on NP-Completeness

Tuesday 11/15: NP-Completeness, Cook-Levin Theorem, More NP-Completeness through Poly-Time Reductions, coNP

Assignments: Watch videos 34-36; PSet 6 published; PSet 5 submitted

PPTX: 34p-NPC-and-CL 35p-more-NPC 36p-co-NP

PDF: 34p-NPC-and-CL 35p-more-NPC 36p-co-NP

Tuesday 11/22 thanksgiving

Thursday 11/24 thanksgiving

Tuesday 11/29 Oracles, Polynomial Hierarchy, Space Complexity, advanced topics on proofs (PCPs, Hardness of Approximation, IPs, Zero-Knowledge)

Assignments: Watch videos 37-39; PSet 7 published; PSet 6 submitted

PPTX: 37p-polynomial-hierarchy 38p-space-complexity 39p-Proofs++

PDF: 37p-polynomial-hierarchy 38p-space-complexity 39p-Proofs++

  • Finish Sipser 7, Sipser 8.2, 9.1, 9.2

Advanced (not required) reading:

Tuesday 12/6: Course Wrap-Up, Computational Lens, Randomness and Pseudorandomness, Algorithmic Fairness

Assignments: Watch videos 40-42; PSet 7 submitted

PPTX: 40p-algorithmic-fairness 41p-Randomness 42p-Parting-Thoughts

PDF: 40p-algorithmic-fairness 41p-Randomness 42p-Parting-Thoughts

Meeting: Ask me Anything

Advanced (not required) reading:


“Complex Communication” by Odelia Sara Lorch