Heribert Vollmer (Leibniz Universität, Hannover, Germany), Circuit complexity
Schedule
- Feb. 2, 2012, 9:00 - 10:30: Arithmetic circuits of small depth
- Feb. 3, 2012, 11:00 - 12:30: Proof complexity
Abstract
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.
Attachments
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.