Theory of Computation

COSC 39, Spring 2025

Main | Schedule | Homeworks | About

Course Schedule

Introduction

3/31

administrivia; what is the purpose of this course? knowledge, skill, philosophy

• Useful resources for reviewing prerequisites:
  • Background knowledge: Sipser Chapter 0
  • Induction: Erickson lecture 1, Appendix I
• Train your thinking and communication skills in math:
  • There’s more to mathematics than rigour and proofs by Terence Tao; here's a video if you prefer him talking in person
  • On writing by Terence Tao
  • Notes on mathematical writing by Clark Barwick
  • Algorithm is not a four-letter word by Jamis Buck
• Universal computation and our mind:
  • Quantum Computing since Democritus by Scott Aaronson. Entertaining, crisp, and original. Try to get a copy from the library.
  • A Turing test for free will by Seth Lloyd
  • What Can Theoretical Computer Science Contribute to the Discussion of Consciousness by Lenore, Manuel, and Avrim Blum
• Why this course?
  • What is the enlightenment I'm supposed to attain after studying finite automata?
  • How practical is Automata Theory?

Languages and Machine Models

4/2

languages, problems, and encoding; regular expressions [scribbles]

• Erickson lecture 2.1–2.3, Sipser Chapter 1.3 regular expressions

4/3

constructing regular expressions [worksheet]

4/4

finite automata and automatic languages: machines with registers [scribbles]

• Erickson lecture 3.1–3.5, Sipser Chapter 1.1

4/7

DFA constructions [worksheet]

Nondeterminism

4/9

regular languages are automatic: nondeterministic finite automata [scribbles]

• Erickson lecture 4.1–4.3, 4.6–4.7, Sipser Chapter 1.2, 1.3 (Theorem 1.54)

4/10

construting NFAs [worksheet]

4/11

power of nondeterminism: closure properties of NFAs [scribbles]

4/14

language transformations and closure properties

Beyond Regularity

4/16

Kleene theorem: where multiple models coincide

• Erickson lecture 4.4–4.5, 4.8–4.9, Sipser Chapter 1.2 (Theorem 1.39), 1.3 (Lemma 1.60)

4/17

constructing regular expressions, reprise

4/18

limits of regularity: fooling sets and Myhill-Nerode theorem; examples of nonregular languages

• Erickson lecture 3.8–3.9

4/21

fooling set constructions

Turing Machines and Decidability

4/23

Turing machine: it's just CPU with memory

• Erickson lecture 6.1–6.7, Sipser Chapter 3
• The Wikipedia page for the Church–Turing thesis is surprisingly detailed
• Things equivalent to Turing machines:
  • Baba Is You
  • Game of Life
  • Magic: The Gathering
  • Powerpoint (Tom Wildenhain is the only person qualified to put Powerpoint under Programming Languages section in his CV.)
  • Minecraft (not surprisingly; but look at its spec/speed!)
  • One single x86 instruction (All the other instructions are fluff! ... and of course, somebody use it to run Doom)
  • ... and many more
• Inception:
  • Game of Life

4/24

Equivalence between different computing devices

4/25

Church-Turing thesis: CPU with memory is universal computation; universality implies incomputability (oh the irony)

• Erickson lecture 6.8, 7.5–7.8, Sipser Chapter 4
• Can you write a program that output the source code of itself?
  • Wikipedia page on Quine
  • Quines (self-replicating programs)
• On halting problem and imcompleteness theorems
  • Gödel, Turing, and Friends
  • Rosser’s Theorem via Turing machines
  • The Surprise Examination Paradox and the Second Incompleteness Theorem

4/28

Is my pseudocode safe?

Resources and Verification

4/30

Time complexity, verification and nondeterminism, P vs NP

• Erickson chapter 12.1–12.2, Sipser Chapter 7.1–7.3

5/1

Midterm 1; no working session today

5/2

NP-hardness and Cook-Levin theorem: no pursuit is useless; mapping and oracle reductions

• Erickson chapter 12.3–12.6, Sipser Chapter 7.4

5/5

Self-reductions

Reductions

5/7

NP-hardness reductions

• Erickson chapter 12.6–12.10, Sipser Chapter 7.5
• There are so much resourses online about NP-hardness I can't even. But here's a few that I find extra helpful:
  • Lecture by Erik Demaine from MIT, including a proof that Super Mario Bros. is NP-hard (and a few other problem we didn't cover in class).
  • P vs. NP and the Computational Complexity Zoo
  • SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete. Super Mario BROOOOOOS.

5/8

More NP-hardness reductions

5/9

Exponential-time hypotheses: No, I mean they are really really hard

• Fine-grained complexity:
  • Fine-Grained Algorithms and Complexity by the Williams at MIT. A full semester course on fine-grained complexity.
  • Fine-Grained Complexity and Algorithm Design, held between Aug 19 – Dec 18, 2015 at Simons Institute. Lots of good talks!
  • On some fine-grained questions in algorithms and complexity by Virginia Vassilevska Williams
  • Lower bounds based on the Exponential Time Hypothesis by Daniel Lokshtanov, Dániel Marx, and Saket Saurabh
  • Hypotheses about Satisfiability and their Consequences by Russell Impagliazzo (Yes, the one who came up with ETH and SETH), streamed on Feb 11, 2021 (last week!)

5/12

(S)ETH reductions

Advanced topics

Randomness

5/14

Randomized algorithm, BPP, and error reduction; polynomial identity testing

• References for randomized algorithm:
  • Randomized Algorithms by Luca Trevisan, Lecture 12
  • Randomized Algorithms by Motwani and Raghavan, Chapter 7.1–7.6

5/15

Fingerprinting

5/16

Pseudorandom generators; hardness is pseudorandomness

• Advanced Complexity Theory by Dana Moshkovitz, Lecture 20–22
• Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Chapter 16.1–16.3
• The longest run of heads by Mark Schilling
• The Mind Reader Game, implemented by by Guy Satat and Ramesh Raskar. Can you beat the computer consistently?

5/19

Have fun with randomness

Communication

5/21

Interactive proofs: why talking to people is important

• Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Chapter 8.1–8.3, 8.5

5/22

[TBD]

5/23

Interactive proof for #P; Cryptography: one-time pad and commitment scheme

• Sipser Chapter 10.4
• Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Chapter 8.5
• Bit Commitment Using Pseudo-Randomness by Moni Naor
• Ciphers:
  • Visual one-time pad
  • One-time Pad by Dirk Rijmenants

5/26

[Memorial Day; no class held] turn everything into polynomials

Onward!

5/28

Zero-knowledge proofs and secure computations

• Theoretical Cryptography, Lecture 1 by Manuel Blum
• A Personal View of Average-Case Complexity by Russell Impagliazzo, 1995
• Zero-knowledge proofs:
  • Zero Knowledge Proof: ELI5 (Halloween Ed.) by Hackernoon
  • Zero Knowledge Proof by Numberphile

5/29

Fun with zero-knowledge proofs

5/30

How does new discovery (like quantum physics and time travel) change our perspective of computation?

• Quantum Computing Since Democritus, Lecture 19: Time Travel by Scott Aaronson
• Harry Potter and the Methods of Rationality, Chapter 17 by Eliezer Yudkowsky, 2010–2015
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent by Scott Aaronson and John Watrous, 2008
• Quantum Computing
  • Quantum Computing Since Democritus, Lecture 9–10 by Scott Aaronson
  • Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Chapter 20
  • A visit from Alice and Bob by Henry Yuen; an amusing story about the breakthrough result MIP* = RE
  • The shape of MIP* = RE by Henry Yuen

6/2

[TBD]