Razborov-Smolensky Lower Bounds for AC0[p] - Graduate Complexity Lecture at CMU

Explore the Razborov--Smolensky lower bounds for AC0[p] in this graduate-level computational complexity theory lecture. Delve into explicit language, key definitions, and theorems, including Fermat's theorem. Learn about gate-by-gate replacement techniques, focusing on Mod3 and Or gates. Examine error bounds and the concept of fixing an X. Engage with exercises on twowise universal hashing and P twiddle. This 73-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 Chapter 14.2.

Introduction
Explicit language
Definitions
Theorems
Fermats theorem
Gate by gate replacement
Mod3 gates
Or gates
Error bound
Fix an X
Exercise
Twowise Universal Hashing
P twiddle