Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche

Circuits, Logic, and Games, 08.11.-11.11.2006

Dagstuhl Seminar Page

List of participants



Thomas Schwentick U. Dortmund, DE
Denis Thérien McGill U., CA
Heribert Vollmer U. Hannover, DE

Description of the Seminars's Topic

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, AC0 (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 AC0 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 AC0 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 AC0 update complexity. This situation might be improved by finding suitable games and combining them with circuit lower bound techniques.

A further important topic in Boolean circuit and function complexity are the computation model of branching programs that have lead to interesting lower bound techniques and results. So far these have not been connected to logic and games. The organizers fels that the seminar would be a good opportunity to remedy this situation.

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.

The organizers asked four participants to present survey talks (of between one and two hours length) early during the meeting. The purpose of these talks was to cover the most important topics and techniques that are currently used in the study of circuit complexity. From these talks, one (J.-E. Pin, Games) had to be cancelled because the speaker could not attend due to the rail strike in France.

The presenters and the topics of the given survey talks are as follows:

  • Eric Allender (Rutgers U., US): Arithmetic circuit complexity
  • Pascal Tesson (Laval U., CA): Algebraic techniques in circuit complexity
  • Nicole Schweikhardt (Humboldt U., DE): The expressive power of numerical predicates

Besides these, the remaining participants were invited to present their recent work and to communicate state-of-the-art advances. There were 16 such communications, each ranging from 30 to 60 minutes. These communications focused on a number of important topics in the complexity of Boolean circuits.

The different approaches, discussed above in the seminar description (the algebraic approach, methods from logic and finite model theory, game-theoretic tools, investigation of branching programs, dynamic complexity) were all very well represented by the different talks given during the 3 days of the seminar:

  • The algebraic approach
    • A. Krebs, Algebraic characterization of TC0
    • H. Straubing, Languages definable with modular quantifiers over $(\mathbb{N},+)$

  • Logic and finite model theory
    • A. Dawar, Model theory on well-behaved structures
    • M. Koucky, Integer addition, circuits, logic, and games
    • N. Immerman, The expressive power of first-order logic with two variables
    • L. Segoufin, FO-definable tree languages

  • Game-theoretic methods
    • M. More, Characterization of Ehrenfeucht-Fraisse equivalence for two classes of finite graphs
    • P. Pudlak, Games and search problems
    • L. Hella, A game for lower bounds on formula size

  • Dynamic complexity
    • W. Hesse, Separation of non-uniform dynamic complexity classes

  • Branching programs
    • M. Sauerhoff, Branching programs: complexity lower bounds by communication games

Two further topics whose relevance the organizers had not anticipated turned out to determine quite a big part of the talks and discussions during the seminar. The first one was the study of arithmetic circuits, as already introduced in the first survey talk by Eric Allender. The second was the study of questions and the use of methods stemming from the area of ``classical'' structural complexity, not so much originally oriented towards the computational model of Boolean circuits.

  • M. Mahajan, Arithmetic classes between NC1 and LOGCFL
  • T. Lee, A rank technique for formula size lower bounds
  • C. Behle, FO[<]-uniformity
  • J. Toran, On the size of Craig interpolants
  • H. Buhrmann, Non-uniform reductions

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).