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, but then things slowed down considerably. No major progress seems to have been made in the last ten years.

As pointed out by Gurevich and Lewis, ACº (the class of all languages accepted by families of Boolean circuits of polynomial size and constant depth) is equivalent to first-order logic. This connection is made even more precise in Immerman's theorem equating uniform ACº with first-order logic with built-in predicates for arithmetic operations (plus and times). In fact, the mentioned results by Furst, Saxe and Sipser that parity is not in ACº was obtained independently by Ajtai making use of model-theoretic arguments. All this indicated that lower bounds in complexity theory might be obtained via inexpressibility results in logic -- an approach pioneered by Fagin. A major method for such inexpressibility results are model-theoretic games. Going back to ideas of Fraïssé and Ehrenfeucht, such games have been very successfully used in the context of first-order logic and some of its fragments and extensions, particularly monadic NP. However, all attempts to apply game-theoretic arguments in the presence of complex predicates, such as addition and multiplication, have been frustrated so far, and here also, progress has slowed down.

On the other hand, other developments in circuit theory and in logic have perhaps not been explored fully in the context of lower bounds. Most important here is the algebraic classification of regular languages. 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 (or other) properties of such languages could be used in lower bound proofs. This also includes investigations of the so-called Crane Beach property; in some cases, but not always, the presence of a neutral letter in a language renders inoperative numerical predicates other than < when this happens, lower bounds argument simplify greatly. Similar techniques have been successfully used in the context of Constraint Databases.

A further area of investigation is the structural complexity of dynamic algorithmic problems. There are, so far, no techniques available to prove that a problem does not have ACº update complexity. This situation might be improved by finding suitable games and combining them with circuit lower bound techniques.

Organization of the Seminar and Activities

Most of the researchers invited to participate responded positively; at the end, the seminar brought together 36 researchers from different areas of complexity theory and logic with complementary expertise. The list of participants consisted of both senior and junior researchers, including a number of postdoctoral researchers and a smaller number of advanced graduate students. Altogether, though originally planned as a “small” half-week seminar, the number of participants almost reached that of a week long seminar.

Concluding Remarks and Future Plans

The organizers think that the Dagstuhl Seminar on Circuits, Logic, and Games was a big success. Bringing together researchers from different areas such of theoretical computer science and logic initiated an interaction and led to fruitful collaborations in attacking some of the open problems in this area.

Also, the participants felt that the Dagstuhl Seminar was very stimulating and provided an impetus for continuing their efforts and interaction in advancing the state-of-the-art in this area. The only negative point that came up in discussions with the organizers was that many participants thought the seminar better would have lasted for a whole week, not only three days. Finally, the organizers wish to sincerely thank the Scientific Directorate of the Center for its support of this event, and hope to have the opportunity to organize a follow-up seminar in the future (this time with a length of one week).