27.09.15 - 02.10.15, Seminar 15401

Circuits, Logic and Games

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

The interplay between circuit complexity and logic is notoriously fruitful: for example, there are tight connections between small-depth circuit classes and fragments and extensions of first-order logic, and ideas from games and finite model theory have provided powerful lower bound techniques for circuits.

In recent years, there has been an impressive growth of interest and activity in the intersection of finite model theory and Boolean circuit complexity. It will be the aim of the seminar to bring together researchers from these two areas to further strengthen the mutual fertilisation.

Specific topics that the seminar will cover are:

  • The algebraic approach to circuit complexity with its applications to finite model theory
  • The logic-circuit connection, with a particular emphasis on circuit lower bounds that trigger results in finite model theory like separations between logics
  • New connections between uniformity conditions on circuit families and logical predicates
  • Structural complexity and circuit lower bounds inherently using methods from logic and algebra
  • Proof systems with low circuit complexity
  • Dynamic complexity: unerstanding the dynamic expressive power of small depth circuit classes

A main goal of the seminar is to work towards complexity-theoretic lower bounds for Boolean circuits, obtained by methods from logic or finite model theory, in particular games.

We hope that the seminar can have a similar impact as the previous Dagstuhl seminars on this topic, by bringing the communities together again to discuss how methods from one area can be fruitfully applied in the other area.