Starting with the seminal paper by Furst, Saxe and Sipser, the last two decades of the previous century saw an immense interest in the computational model of Boolean circuits. Emerging powerful lower bound techniques promised progress towards solutions of major open problems in computational complexity theory. Within a very short time, further progress was made in papers by Fagin et al., Gurevich and Lewis, Håstad, Razborov, Smolensky, and Yao, to mention only a few. The just mentioned result by Furst et al. was obtained independently by Ajtai making use of model-theoretic arguments, and many further lower bounds in complexity have been obtained afterwards making use of inexpressibility results in logic, very often making use of model-theoretic games. After a decade of active research in this direction things slowed down considerably.

In the same way as during the first seminar on Circuits, Logic, and Games (Nov.~2006, 06451), the organizers aimed to bring together researchers from the areas of finite model theory and computational complexity theory, since they felt that perhaps not all developments in circuit theory and in logic had been explored fully in the context of lower bounds. In fact, the interaction between the areas has flourished a lot in the past 2-3 years, as can be exemplified by the following lines of research.

Results of Barrington, Straubing and Thérien show that most circuit classes, if they can be separated at all, can be separated by regular languages - which means that algebraic properties of such languages could be used in lower bound proofs. Recent results prove almost linear upper bounds on the size of circuits for regular languages in many important constant-depth circuit classes, implying that an ω (n^1+?) lower bound success to separate such classes from NC¹. Interesting connections to communication complexity have been obtained in the past two years, showing, e. g., that languages with bounded multiparty communication complexity can be recognized by programs over commutative monoids and thus have very small depth circuit complexity.

While inexpressibility results in finite model theory have been used since the 1980s to obtain circuit lower bounds, recent results make use of circuit lower bounds to separate different logics: The result that number of-variable hierarchy in first -order logic over finite ordered structures is strict was obtained by showing that a certain clique-problem cannot be solved by constant-depth circuits of a certain size.

Further connections between logic and circuits concern uniformity conditions for Boolean circuits: It was proved that in a quite general context, when a circuit based language class is characterized using first- order descriptive complexity, the circuit uniformity conditions spring up in the logic in the form of restrictions on the set of numerical predicates allowed. So called "extensional uniformity conditions" have been studied: Intersecting a non-uniform constant-depth circuit class with a uniform class L (e. g., a formal language class) in some contexts results in a circuit class that can be characterized by first-order logic with L-numerical predicates. (Intuitively, L-numerical predicates are those predicates definable in first-order logic with one "oracle call" to a language from L, i. e., more precisely, with one appearance of a generalized quantifier for such a language.)

While this in principal points out new ways to separate uniformity conditions via logical means, another line of results goes in the opposite direction: It is shown that for a specific arithmetical problem (division), circuits can be constructed that are uniform under much stricter requirements than was anticipated before. Again, the proofs make heavy use of finite model theory.

The workshop brought together 46 researchers from different areas of logic and complexity theory with complementary expertise. The participants consisted of both senior and junior researchers, including a number of postdocs and a few advanced graduate students. Participants were invited to present their work and to communicate state-of-the-art advances. Twenty-seven talks of various lengths took place over the five days of the workshop. Around half of these talks were scheduled prior to workshop, including most of the longer morning talks and tutorials. The remaining slots were filled as the workshop commenced.

The organizers regard the workshop as a great success. The weeklong format was well-suited to a workshop of so broad a scope. Bringing together researchers from different areas of theoretical computer science and logic fostered valuable interactions and led to fruitful collaborations. Feedback from the participants was very positive as well. Finally, the organizers wish to express their gratitude toward the Scientific Directorate of the Center for its support of this workshop, and hope to continue this series of workshops on Circuits, Logic, and Games into the future.