Circuits - Graduate Complexity Lecture 4 at CMU

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.