CS 154: Introduction to Automata and Complexity Theory

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 2017

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


Saba Eskandarian, sabae (at stanford dot edu)
Matthew Jay Katzman, mkatzman (at stanford dot edu)
Daniel Layton Wright, dlwright (at stanford dot edu)
Jimmy Wu, jimmyjwu (at stanford dot edu)

Location and Times:

Tue, Thu 10:30 AM – 11:50 AM at Skilling Auditorium (494 Lomita Mall Stanford)

Book: Michael Sipser, introduction to the theory of computation (2nd or 3rd edition)

Office Hours: Follow on Piazza

HW assignments (follow 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


Tuesday 9/26: Introduction


What are computations? The Computational Lens. Course information and topics. Why Theory? The most fundamental open question of CS: graph coloring ?!? Proof techniques (and an example).

Reading: Chapter 0, Introduction, Sipser


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

Thursday 9/28: Deterministic Finite Automata, Closure Properties, Nondeterminism


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

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


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

PPTX, PDF (to be continued next class)

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

Tuesday  10/10: Finish Minimizing FDA, The Myhill-Nerode Theorem

PPTX, PDF (to be continued next class)

Thursday 10/12: Learning DFAs, Streaming Algorithms

No new PPTX

Tuesday 10/17: Communication Complexity; Starting Turing Machines: deciding vs. recognizing

TMs: PPTX, PDF (to be finished next class)

Thursday 10/19: Multitape TM, Universal Turing Machines, Nondeterministic Turing Machines, Undecidable and Unrecognizable, A_TM is unrecognizable.

PPTX, PDF (to be finished next class)

  • Sipser Section 4, 5

Tuesday 10/24: Mapping Reductions

PPTX, PDF (to be finished next class)

  • Sipser 5.3

Thursday 10/26: Rice’s Theorem, Oracle Machines, Hierarchy of Undecidable Problems, Self Reference

PPTX, PDF (to be finished next class)

  • Note on Rice’s Theorem
  • Sipser 6.1, 6.3

Tuesday 10/31: in-class midterm PDF

Thursday 11/2: Foundation of Mathematics, Kolmogorov Complexity

PPTX, PDF (to be finished next class)

  • Sipser 6.2, 6.4
  • Note on Computability and Logic

Tuesday 11/7: Finish Kolmogorov Complexity, Start Time Complexity


  • Sipser 7 for the next few weeks, 9.1
  • Note on Kolmogorov Complexity

Thursday 11/9: P, NP and Polynomial-Time (Mapping) Reductions


Tuesday 11/14: Cook-Levin Theorem


  • Note on NP-Completeness

Thursday11/16: NP-Completeness through Poly-Time Reductions


Tuesday 11/21: Thanksgiving – no class

Thursday 11/23: Thanksgiving – no class

Tuesday 11/28: coNP, Oracles, Polynomial Hierarchy, Space Complexity


  • Finish Sipser 7, Sipser 8.2 and 9.2

Thursday 11/30: Approximation and Hardness, PCPs, IPs, Zero-Knowledge


Additional (not required) reading:

Tuesday 12/5: Wrap Up


Thursday 12/7: “Ask Me Anything”

Wednesday, December 13, 12:15-3:15 p.m: Finals