Circuits, Logic and Games (Dagstuhl Seminar 15401)

Abstract

Over the years, there has been a lot of interplay between circuit complexity and logic. There are tight connections between small-depth circuit classes and fragments and extensions of firstorder 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 and sustained growth of interest and activity in the intersection of finite model theory and Boolean circuit complexity. The central aim of the seminar was to bring together researchers from these two areas to further strengthen the mutual
fertilisation. The seminar focussed on the following specific topics:
-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: understanding the dynamic expressive power of small depth circuit classes 

The seminar had 43 participants from 11 countries and was very successful with respect to the exchange of recent results, ideas and methodological approaches.