Circuits - Graduate Complexity Lecture 4 at CMU

Explore graduate-level computational complexity theory in this lecture focusing on circuits. Delve into complexity measures, classes, and constant depth circuits. Examine polyoblivious Turing machines, head movement, and uniform construction. Investigate nonuniformity, the Hierarchy Theorem, and hard to compete functions. Analyze circuit lower bounds and exponential time. This 1-hour 20-minute lecture, part of Carnegie Mellon's Course 15-855 (Fall 2017), is taught by Ryan O'Donnell and includes suggested reading from Arora--Barak Chapters 6.1--6.7.

Introduction
Complexity measures
Complexity classes
Constant depth circuits
Poly
oblivious Turing machines
head movement
Turing machine
Uniform construction
Nonuniformity
Hierarchy Theorem
Hard to Compete Functions
Circuit Lower Bounds
Exponential Time
Questions