Interactive Proofs

Fundamental Results

Polynomial Time

Cook-Levin Theorem

Smalll Space

Polynomial Hierarchy

Probabilistic Classes

Reversible Computation

Turing Machines

Completeness

Nondeterminism

Ladner's Theorem

Counting

Randomness

Circuit Complexity

Complexity Theory

Hardness

Satisfiabilty

Karp's List

Polynomial Space

Kolmogorov complexity

Hypercomputation

Computability

Time Complexity

P/NP

Space Complexity

Immerman–Szelepcsényi theorem

Randomized Algorithms

Descriptive complexity theory

15-455 Undergraduate Complexity Theory Carnegie Mellon University Spring 2023 This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.  This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as P, NP, PSPACE. LOG,NLOG, BPP, RP and circuit-based classes.   

15-455 Undergraduate Complexity Theory

Theoretical Computer Science

Strings and encodings

Deterministic finite automaton (DFA)

Church-Turing Thesis

Universality

Stable Matching

Cryptography

Decidability

Boolean Circuits

NP (complexity)

Modular arithmetic

Gödel's Incompleteness Theorems

Graphs

NP-completeness

Group Theory

Probability theory

Fields and Polynomials

Graph Algorithms

Matchings and Bipartite Graphs

Approximation Algorithms

Quantum Computation

15-251 Great Ideas in Theoretical Computer Science Carnegie Mellon University Fall 2018 The course provides a rigorous introduction to the foundations of computer science, improving abstract thinking skills and preparing students to be innovators in the field. Topics include computation, computational complexity, and real-world applications of computational concepts. Prerequisites imply this is an intermediate-level course.  Broadly speaking, the course has several goals. First, it provides a rigorous/formal introduction to the foundations of computer science, which is the science that studies computation in all its generality. An important component of this is improving your analytic and abstract thinking skills since nature's language is mathematics. Second, the course intends to prepare you to be innovators in computer science by presenting some of the great ideas that people in the past have contributed to science and humanity. We hope that you will learn from their examples. Third, the course gives you opportunities to improve your social skills by emphasizing cooperation, clarity of thought, and clarity in the expression of thought.

More specifically, some of the main learning objectives are the following.

- Define mathematically the notions of computation, computational problem, and algorithm.
- Express, analyze and compare the computability and computational complexity of problems.
- Use mathematical tools from set theory, combinatorics, graph theory, probability theory, and number theory in the study of computability, computational complexity, and some of the real-world applications of computational concepts.
- State and explain the important and well-known open problems in the theory of computation.
- Write clearly presented proofs that meet rigorous standards of correctness and conventional guidelines on style.
- Identify and critique proofs that are logically flawed and/or do not meet the expected standards of clarity.
- Cooperate with other people in order to solve challenging and rigorous problems related to the study of computer science.

Note that even though all of the topics we discuss in the course have real-world applications, often we will not be explicitly discussing the applications. This is because initially it is better to separate concerns regarding real-world applications from the exploration of fundamental truths and knowledge that shape how we view and understand the world. The quest for truth and understanding, wherever it takes us, eventually do produce applications, some that we hoped to achieve, and some that were beyond our wildest dreams. The focus of the course is on that quest for truth and understanding, which is arguably more important than specific applications. The formal prerequisites for the course are (15-122 or 15-150) and (21-127 or 21-128 or 15-151). In particular, we expect the students to have taken an introductory computer science course that goes beyond basic computer programming and covers algorithmic thinking. On the mathematics side, we expect the students to have experience reasoning abstractly and know how to write formal proofs. 

15-251 Great Ideas in Theoretical Computer Science