Theory of Computation

COSC 39, Winter 2021

Main | Schedule | Homeworks | About

Course Schedule

Introduction

1/8

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

• 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

1/11

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

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

1/12

constructing regular expressions [worksheet]

1/13

finite automata and automatic languages; are they more powerful than regular expressions? [video|scribbles]

• Erickson lecture 3.1–3.5, Sipser Chapter 1.1

1/15

DFA constructions [worksheet]

Nondeterminism

1/18

(MLK day; no live lectures) tips on induction [video]

• Erickson lecture 3.3; the induction proof for the example there might help you with Homework 1 problem 1.

1/19

induction on strings and automata [worksheet]

1/20

regular languages are automatic: nondeterministic finite automata [video|scribbles]

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

1/22

construting NFAs [worksheet]

Beyond Regularity

1/25

Kleene theorem: where multiple models coincide [video|scribbles]

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

1/26

language transformations and closure properties [worksheet]

1/27

limits of regularity: fooling sets and Myhill-Nerode theorem; examples of nonregular languages [video|scribbles]

• Erickson lecture 3.8–3.9

1/29

fooling set constructions [worksheet]

Turing Machines and Decidability

2/1

Turing machine: it's just CPU with memory [video|scribbles]

• 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

2/2

Equivalence between different computing devices [worksheet]

2/3

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

• 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

2/5

Is my pseudocode safe? [worksheet]

Resources and Verification

2/8

Time complexity, verification and nondeterminism, P vs NP [video|scribbles]

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

2/9

Midterm 1; no working session today

2/10

NP-hardness and Cook-Levin theorem: no pursuit is useless; mapping and oracle reductions [video|scribbles]

• Erickson chapter 12.3–12.6, Sipser Chapter 7.4

2/12

Self-reductions [worksheet]

Reductions

2/15

NP-hardness reductions [video|scribbles]

• 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.

2/16

More NP-hardness reductions [worksheet]

2/17

Exponential-time hypotheses: No, I mean they are really really hard [video|scribbles]

• 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!)

2/19

(S)ETH reductions [worksheet]

Advanced topics

Randomness

2/22

Randomized algorithm, BPP, and error reduction; polynomial identity testing [video|scribbles]

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

2/23

Fingerprinting [worksheet]

2/24

Pseudorandom generators; hardness is pseudorandomness [video|scribbles]

• 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?

2/26

Have fun with randomness [worksheet]

Communication

3/1

Interactive proofs: why talking to people is important [video|scribbles]

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

3/2

Midterm 2; no working session today

3/3

Interactive proof for #P; Cryptography: one-time pad and commitment scheme [video|scribbles]

• 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

3/5

turn everything into polynomials [worksheet]

Onward!

3/8

Zero-knowledge proofs and secure computations [video|scribbles]

• 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

3/9

Fun with zero-knowledge proofs [worksheet]

3/10

How does new discovery (like quantum physics and time travel) change our perspective of computation? [video|scribbles]

• 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

3/16 Tue

Final deadline