Sign inSign in

Circuit complexity

The measure of the resources needed to compute a boolean function using logic circuits, specifically evaluated as family sizes for languages.
as Venkatesan Guruswami defines itCarnegie Mellon UniversityThe wording closest to all 4 definitions
Watch it explained

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

4

Each in their own terms, from the easiest level.

  • Avi Wigderson

    Institute for Advanced Study · Undergraduate

    The study of computing functions using finite sequences of Boolean circuits with Boolean operations.
    • 51:13Mathematics and Computation: The Landscape of P vs. NP
  • Yann LeCun

    New York University · Research

    A field that studies the resources required to compute functions using circuits, where additional layers can exponentially reduce the required hardware.
    • 8:31Learning Representations: A Challenge for Learning Theory, COLT 2013
  • Nicoletta Carabba

    International Centre for Theoretical Physics · Research

    A measure of complexity for quantum states.
    • 9:47Quantum Speed Limits to Operator Flows and Operator Growth

Lectures that assume it

16

The first 12 are shown.

Connections

29

The lectures that define it or assume it, and the concepts next to it.

4 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.