Heribert Vollmer (Leibniz Universität, Hannover, Germany), Circuit complexity


  • Feb. 2, 2012, 9:00 - 10:30: Arithmetic circuits of small depth
  • Feb. 3, 2012, 11:00 - 12:30: Proof complexity


In these introductory lectures we will cover two topics from the area of circuit complexity: In the first lecture we will talk about arithmetic circuits of small depth. We will mainly concentrate on the classes #NC1 and #GapNC1 and show how they provide useful characterizations of counting complexity classes, how they capture the computational complexity of some problems in linear algebra, and how they shed new light on the relation between logarithmic depth circuits and logarithmic space Turing machines. In the second lecture we will turn to the area of proof complexity and use very small NC0 circuit families as proof checkers. Alternatively one might say that we use NC0 circuit families to enumerate languages (allowing repetitions). We will show how on the one hand even NP-complete languages can be enumerated in this way but on the other hand some very simple languages lack this property.