ConceptTheory & Algos
Boolean circuit
A directed acyclic graph where nodes are called gates and edges are called wires, taking inputs and having one output.
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
1Ryan O'Donnell
Lectures that assume it
34The first 12 are shown.
- Approximate counting
- Random Restrictions and AC0 Circuit Lower Bounds
- The Complexity Class NP
- Space Complexity
- Linial-Mansour-Nisan Theorems
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- The Polynomial Hierarchy
- Interactive Proofs: IP=PSPACE
- Razborov Smolensky Lower Bounds for AC0[p]
- Hardness Amplification
- Ironic Complexity
- Search-to-Decision, Padding, Dichotomy Theorems
Connections
43The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Directed acyclic graph
- Boolean function
- Circuit SAT
- Circuit evaluation problem
- Circuit family
- Cook-Levin theorem
Show 1 moreShow fewer
Lectures36
- Computational Models: Circuits
- Boolean Satisfiability (SAT)
- Approximate counting
- Random Restrictions and AC0 Circuit Lower Bounds
- The Complexity Class NP
- Space Complexity
Show 30 moreShow fewer
- Linial-Mansour-Nisan Theorems
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- The Polynomial Hierarchy
- Interactive Proofs: IP=PSPACE
- Razborov Smolensky Lower Bounds for AC0[p]
- Hardness Amplification
- Ironic Complexity
- Search-to-Decision, Padding, Dichotomy Theorems
- Toda's 1st Theorem and the Permanent
- Number Theory II
- Secure Computation and Low-Complexity Cryptography
- Course Introduction and Overview
- Circuits
- Probabilistic Complexity Classes
- NP-Completeness and the Cook-Levin Theorem
- Savitch's Theorem and NL
- From P-Completeness to PSPACE-Completeness
- Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- Oracle Turing Machines and P^NP
- Why is P vs. NP Difficult?
- Hardness vs. Randomness I
- Hardness vs. Randomness II
- Quantum "Supremacy"
- Grover's Algorithm
- Quantum Complexity
- Basics of Quantum Computing
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Monotone Circuit Lower Bounds
- The Polynomial Time Hierarchy
- Quasilinear Cook–Levin Theorem