Theory of Computation === :closed_book: 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). :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 --- ### 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). -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). ### 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](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) 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: ?* ### 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 ( 1-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), Mapping reductions (see Omer Reingold's course lecture on Mapping reductions [here](https://www.youtube.com/watch?v=_0163dZIBvw&t=1593s&ab_channel=CS154-IntroductiontotheTheoryofComputing). 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. **[Optional] Topic:** Self reference + foundation of mathematics. 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) <!-- 16. **[Optional] Topic:** Kolmogorov Complexity (1 lecture). *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. (1-2 lectures) *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: ?*. 19. **Topic**: Definition of NL, s-t connectivity in NL and NL=co-NL (1+ lecture). *Lecturer: ?*. 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) *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 toc.compilation@gmail.com 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).
Last changed by  
 
Alex Tang
1444

Read more

Theory of Computation

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

5/21/2022
Agnostic Learning with Bias

References https://arxiv.org/pdf/2005.14426.pdf https://arxiv.org/pdf/2106.01101.pdf Notations $\widetilde{w} \in \mathbb{R}^d$, $w = [\widetilde{w}, b_w] \in \mathbb{R}^{d+1}$, similarly for other vectors. $x = [\widetilde{x}, 1] \in \mathbb{R}^{d+1}$ $\theta = \arccos(\dfrac{\widetilde{w}^\top\widetilde{v}}{|\widetilde{w}||\widetilde{v}|})$

11/3/2021
Read more from Alex Tang
Published on HackMD