University of Califoia, 1992, -154 pp.
These lecture notes were written for a topics course in the Mathematics Department at the University of Califoia, San Diego during the winter and spring quarters of 1992.
Introduction to circuit complexity.
Theorems of Shannon and Lupanov giving upper and lower bounds of circuit complexity of almost all Boolean functions.
Spira's theorem relating depth and formula size.
Khrapchenko's lower bound on formula size over AND/OR/NOT.
Neciporuk's theorem.
Simulation of time bounded TM's by circuits.
NC/AC hierarchy.
Circuit value problem.
Depth restricted circuits for space bounded Turing machines.
Circuits for parallel prefix vector addition and for symmetric functions.
Schnorr's 2n-3 lower bound on circuit size.
Blum's 3n-o(n) lower bound on circuit size.
Subbotovskaya's theorem.
Andreev's n2.5 lower bound on formula size with AND/OR/NOT.
Hastad's switching lemma.
Applications of Hastad's Lemma.
Constant depth reducibilities (Chandra-Stockmeyer-Vishkin).
Smolensky's theorem.
Probabalistic Circuits.
Valiant-Vazirani Theorem.
Theorems of Toda and Allender-Hertrampf.
Uniform circuit families, unbounded and bounded fanin.
Conclusion of uniformity for AC0.
Linear-time Hierarchy.
Multiplication is in constant-alteation linear time.
Log depth circuits for division.
These lecture notes were written for a topics course in the Mathematics Department at the University of Califoia, San Diego during the winter and spring quarters of 1992.
Introduction to circuit complexity.
Theorems of Shannon and Lupanov giving upper and lower bounds of circuit complexity of almost all Boolean functions.
Spira's theorem relating depth and formula size.
Khrapchenko's lower bound on formula size over AND/OR/NOT.
Neciporuk's theorem.
Simulation of time bounded TM's by circuits.
NC/AC hierarchy.
Circuit value problem.
Depth restricted circuits for space bounded Turing machines.
Circuits for parallel prefix vector addition and for symmetric functions.
Schnorr's 2n-3 lower bound on circuit size.
Blum's 3n-o(n) lower bound on circuit size.
Subbotovskaya's theorem.
Andreev's n2.5 lower bound on formula size with AND/OR/NOT.
Hastad's switching lemma.
Applications of Hastad's Lemma.
Constant depth reducibilities (Chandra-Stockmeyer-Vishkin).
Smolensky's theorem.
Probabalistic Circuits.
Valiant-Vazirani Theorem.
Theorems of Toda and Allender-Hertrampf.
Uniform circuit families, unbounded and bounded fanin.
Conclusion of uniformity for AC0.
Linear-time Hierarchy.
Multiplication is in constant-alteation linear time.
Log depth circuits for division.