Theory of Computation

Description

This is a collection of videos that can be used for an undergraduate Theory of Computation course. We hope that this collection of videos would be a useful community resource. The intent is that these videos can be used in a flipped class format. The instructor can choose to use these videos in whatever fashion he/she thinks best. These videos will ideally be supplemented by classroom discussion, practice exercises and assignments as part of the course (please contact us if you would like access to some of these exercises).

Textbook

Main Reference: Introduction to the Theory of Computation by Sipser, Michael.

Other references: Introduction to Theoretical Computer Science by Barak, Boaz. Accessible here: https://introtcs.org/public/index.html

List of Topics and Lecturers

Part -I: Prerequisites

-3. Topic: Asymptotics (1 lecture)
Lecturer: Jason Hartline.
Video links: Introduction, Big-oh, Exact bounds, Lower bounds, strict bounds, Big-oh and Logarithms.

-2. Topic: Mathematical Induction (refresher).
Lecturer: Aravindan Vijayaraghavan
Video links: Induction - part 1, Induction-part 2

-1. Topic: Probability refresher (from Grad algorithms)
Lecturer: Konstantin Makarychev
Video links: Probability, Random variables

Part 0: Warmup

0. Topic: Warmup and Infinite Sets (1 lecture).
   Lecturer: Aravindan Vijayaraghavan.
   Infinite Sets, Comparing cardinalities using maps, and Diagonalization.
   Video links: Introduction, Cardinalities of Infinite Sets and Maps, Diagonalization.

Part I. Finite Automata, Regular Languages

1. Topic: DFA, NFA, Regular Languages and closure properties, and regular expressions (2-3 lectures).
   Lecturer: Omer Reingold
   Video links: Introduction, DFA, Regular Languages and Closure Properties - Take 1, NFA, Equivalence between DFA and NFA, Closure Properties - Take 2, Regular expressions .
2. Topic: Pumping lemma (1 lecture).
   Lecturer: Richard Cole.
   Video links: Introduction, Non-regular Languages, Proof of Pumping Lemma, Applications
3. Topic: Myhill-Nerode theorem and DFA minimization (2 lectures).
   Lecturer: Anindya De.
   Video links: Introduction, Equivalence Relations, Proof of Myhill-Nerode Theorem, DFA Minimization
4. Topic: Streaming lower bounds (1 lecture).
   Lecturer: Amir Yehudayoff.
   Video links: Introduction, Streaming and Automata, Communication
5. [Optional] Topic: Context-Free Languages.
   Lecturer: ?

Part II. Turing Machines.

6. Topic: Turing Machines — Definition, An example, Turing-recognizability (recursive enumerability), Decidability (1-2 lectures).
   Lecturer: Swastik Kopparty.
   Video links: Introduction, Turing Recognizability, Turing Decidability Part 1, Turing Decidability Part 2
7. Topic: Variants of TM, Church Turing thesis, Universal Turing Machine and many-one reductions ( 1-2 lectures).
   Lecturer: Eric Allender.
   Video links: Introduction, Variants of TM, The Church-Turing Thesis, Undecidable Problems
8. Topic: Undecidability of Halting problem and non-Turing-recognizability of complement of Halting (
   $A_{TM}$ may be more natural), more examples of non-recognizability and undecidable languages through reductions and Rice’s theorem (2 lectures).
   Lecturer: Tal Malkin.
   Video links: Introduction, Halting Problems, Rice's Theorem, Mapping reductions (see Omer Reingold's course lecture on Mapping reductions here.
9. Topic: Oracle Machines (Turing Reductions), Hierarchy of Undecidable Problems (1 lecture).
   Lecturer: Eshan Chattopadhyay.
   Video links: Introduction, Oracle Machines, Hierarchy of Undecidable Problems
10. [Optional] Topic: Self reference + foundation of mathematics.
11. Topic: Kolmogorov Complexity (1 lecture).
    Lecturer: Donald Stull
    Video links: Introduction to Kolmogorov Complexity, The Invariance Theorem of Kolmogorov Complexity, Kolmogorov complexity of Random Strings and Undecidability

Part III. Complexity Theory

12. Topic: Definition of time complexity, P, NP and polynomial time reductions, time hierarchy theorem. (1-2 lectures)
    Lecturer: Aravindan Vijayaraghavan.
    Video links: Time Complexity, P and NP, Polynomial Time Reductions
13. Topic: NP-completeness, Cook-Levin theorem (1 lecture).
    Lecturer: Chris Umans.
    Video links: Introduction, Circuit SAT, 3-SAT
14. Topic: More NP-completeness — including Independent Set, Clique, Vertex Cover, Subset-sum, Steiner tree (2 lectures).
    Lecturer: Jason Hartline.
    Video links: Hardness Reductions, 3-SAT to INDEP-SET, 3-SAT to HAMILTONIAN-CYCLE,
    3-SAT to 3D-MATCHING
15. Topic: Space complexity, PSPACE completeness, Savitch’s theorem (1+ lecture).
    Lecturer: ?.
16. Topic: Definition of NL, s-t connectivity in NL and NL=co-NL (1+ lecture).
    Lecturer: ?.
17. Topic: Randomized algorithms, RP, BPP and BPP in EXP (1 lecture).
    Lecturer: David Zuckerman.
    Video links: Introduction, RP and BPP, Derandomization
18. Topic: Basics of circuit complexity, Definition of P/poly and P in P/poly (1 lecture).
    Lecturer: Ben Rossman.
    Video Links: Introduction, Basics of Circuits, P in P/poly

Remark: Lectures marked with a "?" are those without an assigned lecturer. Volunteers for recording this lecture would be much appreciated.

Contact

Compiled by Anindya De, Jason Hartline, Omer Reingold, Aravindan Vijayaraghavan. Please email [e-mail] or contact either Jason or Aravindan for access to the page with example exercises.

If you're interested in contributing lecture videos to this compilation on any of these topics (particularly ones that haven't been covered), please get in touch with us (before you record your videos).