Theory of Computation
===

###### tags: `ToC`

:::info
- TBD
:::

:closed_book: Description
---

The goal is to build a collection of videos for an undergraduate Theory of Computation course. We hope that this collection of videos would be a useful community resource for flipped classes. The intent is that these videos can be used in a flipped class format. The flipped format has been quite successful for other topics and seems well suited to remote teaching that many of us are doing. 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.

:books: 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

:books: List of Topics and Lecturers (tentative)
---

### Part -I: Prerequisites
-3. **Topic:** Asymptotics (1 lecture)
*Lecturer: Jason Hartline*.
*Video links:* [Introduction](https://youtu.be/r57VXrHqba0), [Big-oh](https://youtu.be/oGjuv7WnHy4), [Exact bounds, Lower bounds, strict bounds](https://youtu.be/qeUXFmx_up0), [Big-oh and Logarithms](https://youtu.be/qt_zuc01l0o).
*Example Exercises:* [here](https://hackmd.io/dzG0zJdVScid6AFJxSShyA)

-2. **Topic:** Mathematical Induction (refresher).
*Lecturer: Aravindan Vijayaraghavan*
*Video links*: [Induction - part 1](https://youtu.be/hvtICWEfuFs), [Induction-part 2](https://youtu.be/C7e2TqowXMI)

-1. **Topic:** Probability refresher (from Grad algorithms)
*Lecturer: Konstantin Makarychev*
*Video links*: [Probability, Random variables]( https://youtu.be/WhqOsrY1PrA)

### 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](https://youtu.be/trn6mdEKDwY), [Cardinalities of Infinite Sets and Maps](https://youtu.be/hzlDtABqgKc), [Diagonalization](https://youtu.be/ocUFLS1ausw).
*Example Exercises: [here](https://hackmd.io/eLcUWJxRSTyX51n3EGYVpA)*

### Part I. Finite Automata, Regular Languages ###

1. **Topic**: DFA, NFA, Regular Languages and closure properties, and regular expressions (2 lectures).
*Lecturer: Omer Reingold*
*Video links:* [Introduction](https://youtu.be/hI8HW0K29a4), [DFA](https://youtu.be/LmOLi2j2uBY), [Regular Languages and Closure Properties - Take 1](https://youtu.be/_s8LcC1W6X8), [NFA](https://youtu.be/-4rTVv0Ec5Q), [Equivalence between DFA and NFA](https://youtu.be/m2PyKQtFSys), [Closure Properties - Take 2](https://youtu.be/7J9WQO1BwL0), [Regular expressions](https://youtu.be/O0hy0rie_YM) .
3. **Topic**: Pumping lemma (1 lecture).
*Lecturer: Richard Cole*.
*Video links:* [Introduction](https://youtu.be/zFRpg2msk5M), [Non-regular Languages](https://youtu.be/9WvR3rp58nM), [Proof of Pumping Lemma](https://youtu.be/tX1kGTQxNbM), [Applications](https://youtu.be/rZhc1QoPqq0)
*Example Exercises: [here](https://hackmd.io/@KLRR45cEQvax47XEu68YLA/HyJ1RW_rD)*
5. **Topic**: Myhill-Nerode theorem and DFA minimization (2 lectures).
*Lecturer: Anindya De*.
*Video links:* [Introduction](https://youtu.be/VOI5pUbj5CA), [Equivalence Relations](https://youtu.be/ijNnEPDHons), [Proof of Myhill-Nerode Theorem](https://youtu.be/0Dxr5a7TIp8), [DFA Minimization](https://youtu.be/1UPOGapxA6E)
7. **Topic**: Streaming lower bounds (1 lecture).
*Lecturer: Amir Yehudayoff.*
*Video links:* [Introduction](https://youtu.be/nQW9wbq8Lv4), [Streaming and Automata](https://youtu.be/GB36iSM1TlY), [Communication](https://youtu.be/DvkfgaLZZqc)
9. **[Optional] Topic**: Context-Free Languages.
*Lecturer: TBA*

### 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](https://youtu.be/TU0KZ2qSo30), [Turing Recognizability](https://youtu.be/7yte6NEUULo), [Turing Decidability Part 1](https://youtu.be/oNZwO3AVYRY), [Turing Decidability Part 2](https://youtu.be/FYfsDPRfCTA)
9. **Topic:** Variants of TM, Church Turing thesis, Universal Turing Machine and many-one reductions (~ 2 lectures).
*Lecturer: Eric Allender*.
*Video links:* [Introduction](https://youtu.be/RyA0lKs8TNQ), [Variants of TM](https://youtu.be/2Zz3xdQRUA8), [The Church-Turing Thesis](https://youtu.be/eaDPg-AVPBY), [Undecidable Problems](https://youtu.be/BxvVEofgEtU)
11. **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](https://youtu.be/TqCYvaBN3Eo), [Halting Problems](https://youtu.be/fzhGthN_vno), [Rice's Theorem](https://youtu.be/Vc_Tx9DVg1Q)
12. **Topic:** Oracle Machines (Turing Reductions), Hierarchy of Undecidable Problems (1 lecture).
*Lecturer: Eshan Chattopadhyay*.
*Video links:* [Introduction](https://youtu.be/bB9BNoe3Y94), [Oracle Machines](https://youtu.be/YFdIPd5Z4Eo), [Hierarchy of Undecidable Problems](https://youtu.be/JEuyESKPOhk)
14. **Topic:** Self reference + foundation of mathematics (1 lecture).
Lecturer: TBA.
15. **Topic:** Kolmogorov Complexity (1 lecture).
*Lecturer: Donald Stull*
*Video links:* [Introduction to Kolmogorov Complexity](https://youtu.be/XT-OXOlUyRw), [The Invariance Theorem of Kolmogorov Complexity](https://youtu.be/1g0w40bxKDo), [Kolmogorov complexity of Random Strings and Undecidability](https://youtu.be/y8_mGoaUvYM)
Example exercises: [Link](https://hackmd.io/@KLRR45cEQvax47XEu68YLA/H1XP6JwPc)
<!-- *Lecturer: Ilya Volkovich (To be posted)*.
*Video link:* [Kolmogorov complexity](https://umich.zoom.us/rec/play/7FaWM_Y2EuTcj4OJ2nxVxtUOIaKgLcLu-9X-pV9-sRzrtkL7bjpPJKjQQT3psLZRh8JglVD2ecOJV5Fx.G8fRDe6lTJeiW1UX?startTime=1602696691000&_x_zm_rtaid=rfpGrME9Sjm-tc6dXkWduw.1613002550431.e8c7aad117e0cf71764b19f8e634f248&_x_zm_rhtaid=864) (video format is different, and is hosted on the UMich server)
-->

### Part III. Complexity Theory ###

12. **Topic**: Definition of time complexity, P, NP and polynomial time reductions, time hierarchy theorem (optional).
*Lecturer: Aravindan Vijayaraghavan*.
*Video links:* [Time Complexity](https://youtu.be/ua24tOzfM14), [P and NP](https://youtu.be/sUPY-RG3Dd4), [Polynomial Time Reductions](https://youtu.be/Vioy2hhNb1E)
15. **Topic**: NP-completeness, Cook-Levin theorem (1 lecture).
*Lecturer: Chris Umans.*
*Video links:* [Introduction](https://youtu.be/OuaiRp9oxIA), [Circuit SAT](https://youtu.be/GzAkW_QePE8), [3-SAT](https://youtu.be/V8MChnBxS_s)
16. **Topic**: More NP-completeness — including Independent Set, Clique, Vertex Cover, Subset-sum, Steiner tree (2 lectures).
*Lecturer: Jason Hartline*.
*Video links:* [Hardness Reductions]( https://youtu.be/yzpvFTi9rXQ), [3-SAT to INDEP-SET](https://youtu.be/l50kaOevBdQ), [3-SAT to HAMILTONIAN-CYCLE](https://youtu.be/Y-71Zmw2LRE),
[3-SAT to 3D-MATCHING](https://youtu.be/5d_t-R-pxns)
17. **Topic**: Space complexity, PSPACE completeness, Savitch’s theorem (1+ lecture).
*Lecturer: Pravesh Kothari*.
19. **Topic**: Definition of NL, s-t connectivity in NL and NL=co-NL (1+ lecture).
*Lecturer: Prasad Raghavendra*.
21. **Topic**: Randomized algorithms, RP, BPP and BPP in EXP (1 lecture).
*Lecturer: David Zuckerman*.
*Video links:* [Introduction](https://youtu.be/dfOa4asJHxI), [RP and BPP](https://youtu.be/rG3nLNrO3MY), [Derandomization](https://youtu.be/YhaWlUaFOdA)
23. **Topic**: Basics of circuit complexity, Definition of P/poly and P in P/poly (1 lecture).
*Lecturer: Ben Rossman*.
*Video Links:* [Introduction](https://youtu.be/KYwl-H-lt0g), [Basics of Circuits](https://youtu.be/HYd4By5M62A), [P in P/poly](https://youtu.be/V0gMxcFCJXE)

Please let us know if you would like to volunteer lectures on other topics that are not covered here, or unassigned topics.