Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMU

This is a graduate-level lecture on computational complexity, specifically focusing on the Razborov-Smolensky lower bounds for AC0 circuits with mod p gates. The lecturer, Ryan O’Donnell, begins by reviewing the historical context, including Håstad’s lower bound for parity in AC0, and then introduces the main results: Razborov’s 1987 result showing that majority requires exponential size circuits with AND, OR, NOT, and parity gates, and Smolensky’s generalization to mod p gates. The lecture then outlines the proof strategy, which involves approximating constant-depth circuits with low-degree polynomials over finite fields. The key theorem states that any Boolean function computable by a depth-D, size-S circuit with AND, OR, NOT, and mod 3 gates can be approximated by a randomized polynomial of degree O(log S)^D, with high accuracy. The proof proceeds by replacing each gate with a corresponding polynomial, handling AND, NOT, and mod 3 gates directly, and using a more complex construction for OR gates. The lecture also discusses the limitations of these techniques, such as the inability to handle mod 6 gates due to the lack of a field of size 6, and mentions Ryan Williams’ 2011 result on lower bounds for NEXP. The second theorem shows that no low-degree polynomial over F3 can approximate the parity function on more than 99% of inputs, leading to the final lower bound: any depth-D circuit computing parity with mod 3 gates must have size exponential in N^(1/2D). The lecture concludes with a discussion of open problems and the state of circuit lower bounds.