Home

Welcome to the website!

Lectures

1. Introduction to Information Theory and Computational Complexity
2. Lecture Notes: Complexity Theory
3. Information Theory and Learning Algorithms - Lecture Notes
4. Information Theory and Coding
5. Uniquely Decodable Codes and Prefix Codes
6. Stationary and Memoryless Sources: Coding and Entropy
7. Lecture Notes: Information Theory and Kolmogorov Complexity
8. Kolmogorov Complexity and Its Relation to Shannon Entropy
9. Introduction to Classical Complexity Theory
10. Turing Machines and Complexity Theory
11. Turing Machines: Speed Up Theorem and Space Complexity
12. Lecture Notes: Non-deterministic Turing Machines and Complexity Classes
13. Lecture Notes: Undecidability, Complexity Classes, and Proper Complexity Functions
14. Proof of the Time Hierarchy Theorem
15. Complexity Classes and Relationships: Reachability Method and Savitch’s Theorem
16. Non-deterministic Space Complexity and the Immerman-Szelepcsényi Theorem
17. Complete Problems and Reductions in Complexity Theory
18. Reduction, Completeness, and the Cook-Levin Theorem
19. NP-Completeness and Reductions
20. NP-Complete Problems and Related Concepts
21. Complexity Theory: L-Completeness, NL-Completeness, and the Polynomial Hierarchy
22. Lecture Notes: Polynomial Hierarchy and Related Concepts