ConceptTheory & Algos
Circuit complexity
The measure of the resources needed to compute a boolean function using logic circuits, specifically evaluated as family sizes for languages.
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
4Each in their own terms, from the easiest level.
Avi Wigderson
The study of computing functions using finite sequences of Boolean circuits with Boolean operations.Yann LeCun
A field that studies the resources required to compute functions using circuits, where additional layers can exponentially reduce the required hardware.Nicoletta Carabba
A measure of complexity for quantum states.
Lectures that assume it
16The first 12 are shown.
- Grover's Algorithm
- Random Restrictions and AC0 Circuit Lower Bounds
- Time/Space Tradeoffs for SAT
- Razborov Smolensky Lower Bounds for AC0[p]
- Hardness Amplification
- Ironic Complexity
- Instance Checking and the Permanent
- Secure Computation and Low-Complexity Cryptography
- Course Introduction and Overview
- Oracle Turing Machines and P^NP
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Hardness vs. Randomness I
Connections
29The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Turing machine
- Boolean circuit
- Complexity theory
- Quantum state
- Circuit lower bounds
- Pseudorandom generator
Show 3 moreShow fewer
Lectures20
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Learning Representations: A Challenge for Learning Theory, COLT 2013
- Mathematics and Computation: The Landscape of P vs. NP
- Quantum Speed Limits to Operator Flows and Operator Growth
- Grover's Algorithm
- Random Restrictions and AC0 Circuit Lower Bounds
Show 14 moreShow fewer
- Time/Space Tradeoffs for SAT
- Razborov Smolensky Lower Bounds for AC0[p]
- Hardness Amplification
- Ironic Complexity
- Instance Checking and the Permanent
- Secure Computation and Low-Complexity Cryptography
- Course Introduction and Overview
- Oracle Turing Machines and P^NP
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Hardness vs. Randomness I
- Hardness vs. Randomness II
- Quantum "Supremacy"
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Quasilinear Cook–Levin Theorem