Day 18

First half of Razborov-Smolensky proof that depth d circuits of Mod₃, AND, OR and NOT gates computing parity must have an exponential number of gates.

Links:

• We've been following the proof in Boppana-Sipser
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity by Roman Smolensky
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition by Alexander Razborov