Theoretical Computer Science
Algorithms, complexity, computation, and the mathematical foundations of computing.
Foundational CS theory — what can be computed, how efficiently, and why. Browse the subtopics below.
Subtopics
Notes
- Advanced Topics in Classical Complexity Theory
- Automata and Formal Languages
- Boolean Fourier Analysis and Complexity Measures of Boolean Functions
- Expander Graphs — Fundamentals
- Explicit Constructions of ε-Biased Distributions and Error-Correcting Codes
- Hierarchy Theorems, Relativization, and Circuit Complexity
- Hypercontractivity and Small-Set Expansion
- Interactive Proofs and the PCP Theorem
- Mathematical Preliminaries for the Theory of Computation
- Pseudorandomness — Expander Chernoff and ε-Biased Distributions
- Quantum Complexity Theory
- Reducibility and Advanced Computability Theory
- Space Complexity and Savitch's Theorem
- The Zig-Zag Product and SL = L
- Time Complexity — P, NP, and NP-Completeness
- Turing Machines and Decidability
- Kolmogorov Complexity
- Universal Source Coding
- Data Compression and Source Coding