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).
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Michael Bauland (Leibniz Universität Hannover, DE)
- Christoph Behle (Universität Tübingen, DE)
- Beate Bollig (TU Dortmund, DE) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Lauri Hella (University of Tampere, FI) [dblp]
- William Hesse (Clarkson University - Potsdam, US)
- Neil Immerman (University of Massachusetts - Amherst, US) [dblp]
- Jan Johannsen (LMU München, DE) [dblp]
- Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
- Andreas Krebs (Universität Tübingen, DE) [dblp]
- Troy Lee (CWI - Amsterdam, NL) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
- Marcel Marquardt (Universität Mainz, DE)
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Mark Mercer (McGill University - Montreal, CA)
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- Malika More (Clermont University, FR)
- Pavel Pudlák (Czech Academy of Sciences, CZ) [dblp]
- Martin Sauerhoff (TU Dortmund, DE)
- Henning Schnoor (Universität Kiel, DE) [dblp]
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Nicole Schweikardt (HU Berlin, DE) [dblp]
- Thomas Schwentick (TU Dortmund, DE) [dblp]
- Luc Segoufin (University of Paris South XI, FR) [dblp]
- Detlef Sieling (TU Dortmund, DE)
- Iain A. Stewart (Durham University, GB) [dblp]
- Howard Straubing (Boston College, US) [dblp]
- Pascal Tesson (Laval University - Quebec, CA)
- Denis Therien (McGill University - Montreal, CA) [dblp]
- Michael Thomas (Leibniz Universität Hannover, DE)
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Falk Unger (CWI - Amsterdam, NL)
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Thomas Wilke (Universität Kiel, DE) [dblp]
- data structures/algorithms/complexity
- computational complexity theory
- finite model theory
- Boolean circuits
- regular languages
- finite monoids