ConceptTheory & Algos
Complexity theory
Complexity theory investigates what is computable in practice, focusing on resources like time and space required by algorithms.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
Showing that various computational tasks actually do not have efficient algorithms, or finding lower bounds for the complexity of problems.
Lectures that assume it
35The first 12 are shown.
- Computational Indistinguishability
- Grover's Algorithm
- Approximate counting
- The RSA Cryptosystem and Efficient Exponentiation
- A Solution to the Stable Marriage Problem
- Green HPC: Paving the Way for Sustainable Supercomputing
- Complexity and Computability with Closed Timelike Curves
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Interactive Proofs: IP=PSPACE
- Learning Representations: A Challenge for Learning Theory, COLT 2013
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
Connections
45The lectures that define it or assume it, and the concepts next to it.
Concepts8
- Algorithms theory
- Computability theory
- Efficiency
- #SAT in IP protocol verification
- Advice classes
- Algebraic complexity theory
Show 2 moreShow fewer
Lectures37
- Introduction, Finite Automata, Regular Expressions
- Course Introduction and Overview
- Computational Indistinguishability
- Grover's Algorithm
- Approximate counting
- The RSA Cryptosystem and Efficient Exponentiation
Show 31 moreShow fewer
- A Solution to the Stable Marriage Problem
- Green HPC: Paving the Way for Sustainable Supercomputing
- Complexity and Computability with Closed Timelike Curves
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Interactive Proofs: IP=PSPACE
- Learning Representations: A Challenge for Learning Theory, COLT 2013
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
- Cook-Levin Theorem
- Efficient Fine-Grained Algorithms
- IP = PSPACE
- Linear Programming: Optimization Reduces to Feasibility
- Why is P vs. NP Difficult?
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Quantum "Supremacy"
- Emergence and Complexity
- Problems in P
- Convex Optimization II: Analytic Center Cutting-Plane and Ellipsoid Methods
- Grover's Algorithm
- Rotate, Compute, Rotate
- Algebraic Circuit Complexity
- Constraint Satisfaction Problems
- coNP is a Subset of IP
- Beyond Worst-Case Analysis
- How to do CS Theory
- Probabilistically Checkable Proofs of Proximity
- Super Turing Computing: Foundations for Aware and Ever-Adapting Systems
- More on constant-round interactive proof systems
- What Can the Theory of Cryptography Tell Us About AI Verification?
- Cryptographic Proofs, Lattices & Hardness Assumptions: A Polylogue
- Exploring System Dynamics in the Natural World with AI