ConceptTheory & Algos
Circuit
A combinatorial object with a set of boolean inputs and one output bit, containing gates like AND, OR, and NOT.
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.
Boolean logic1Languages as 0-1 strings1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
1Lectures that assume it
17The first 12 are shown.
- The Word RAM Model
- Random Restrictions and AC0 Circuit Lower Bounds
- Measurement and Timing
- Simon's Algorithm
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Hardness Amplification
- Hard Lefschetz Theorem and Hodge-Riemann Relations for Combinatorial Geometries
- Secure Computation and Low-Complexity Cryptography
- Course Introduction and Overview
- Hardness vs. Randomness I
- Hardness vs. Randomness II
- ISA and Microarchitecture
Connections
23The lectures that define it or assume it, and the concepts next to it.
Concepts5
Lectures18
- Circuits
- The Word RAM Model
- Random Restrictions and AC0 Circuit Lower Bounds
- Measurement and Timing
- Simon's Algorithm
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
Show 12 moreShow fewer
- Hardness Amplification
- Hard Lefschetz Theorem and Hodge-Riemann Relations for Combinatorial Geometries
- Secure Computation and Low-Complexity Cryptography
- Course Introduction and Overview
- Hardness vs. Randomness I
- Hardness vs. Randomness II
- ISA and Microarchitecture
- Inputs, Outputs, and Symmetric Matrices in Linear Dynamical Systems
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Algebraic Circuit Complexity
- Quasilinear Cook–Levin Theorem
- Cryptographic Proofs, Lattices & Hardness Assumptions: A Polylogue