TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 10061

Circuits, Logic, and Games

( Feb 07 – Feb 12, 2010 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/10061

Organizers

Contact


Schedule

Summary

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 ω (n1+?) lower bound success to separate such classes from NC1. 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.


Participants
  • Sreejith Ajithkumar (The Institute of Mathematical Sciences, IN)
  • Christoph Behle (Universität Tübingen, DE)
  • Olaf Beyersdorff (Leibniz Universität Hannover, DE) [dblp]
  • Arkadev Chattopadhyay (University of Toronto, CA) [dblp]
  • Thomas Colcombet (University of Paris VII, FR) [dblp]
  • Samir Datta (Chennai Mathematical Institute, IN) [dblp]
  • Arnaud Durand (University Paris-Diderot, FR) [dblp]
  • Kousha Etessami (University of Edinburgh, GB) [dblp]
  • Nicola Galesi (Sapienza University of Rome, IT) [dblp]
  • Etienne Grandjean (Caen University, FR) [dblp]
  • Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
  • Lauri Hella (University of Tampere, FI) [dblp]
  • Neil Immerman (University of Massachusetts - Amherst, US) [dblp]
  • Jan Johannsen (LMU München, DE) [dblp]
  • Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
  • Juha Kontinen (University of Helsinki, FI) [dblp]
  • Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Andreas Krebs (Universität Tübingen, DE) [dblp]
  • Klaus-Jörn Lange (Universität Tübingen, DE) [dblp]
  • Peter Lohmann (Leibniz Universität Hannover, DE)
  • Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
  • Oliver Matz (ppi Media GmbH - Kiel, DE)
  • Pierre McKenzie (University of Montréal, CA) [dblp]
  • Arne Meier (Leibniz Universität Hannover, DE) [dblp]
  • Peter Bro Miltersen (Aarhus University, DK) [dblp]
  • David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
  • Jean-Eric Pin (University of Paris VII, FR) [dblp]
  • Pavel Pudlák (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Raghavendra Rao B.V. (Universität des Saarlandes, DE) [dblp]
  • Benjamin Rossman (MIT - Cambridge, US) [dblp]
  • Rahul Santhanam (University of Edinburgh, GB) [dblp]
  • Nicole Schweikardt (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Thomas Schwentick (TU Dortmund, DE) [dblp]
  • Luc Segoufin (ENS - Cachan, FR) [dblp]
  • Srikanth Srinivasan (Institute of Advanced Study - Princeton, US) [dblp]
  • Iain A. Stewart (Durham University, GB) [dblp]
  • Howard Straubing (Boston College, US) [dblp]
  • Balder Ten Cate (University of California - Santa Cruz, US) [dblp]
  • Thomas Thierauf (Hochschule Aalen, DE) [dblp]
  • Michael Thomas (Leibniz Universität Hannover, DE)
  • Wolfgang Thomas (RWTH Aachen, DE) [dblp]
  • Jacobo Torán (Universität Ulm, DE) [dblp]
  • Jouko Väänänen (University of Helsinki, FI) [dblp]
  • Jan Van den Bussche (Hasselt University - Diepenbeek, BE) [dblp]
  • Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
  • Thomas Zeume (TU Dortmund, DE) [dblp]

Related Seminars
  • Dagstuhl Seminar 06451: Circuits, Logic, and Games (2006-11-08 - 2006-11-10) (Details)
  • Dagstuhl Seminar 15401: Circuits, Logic and Games (2015-09-27 - 2015-10-02) (Details)

Classification
  • data structures/algorithms/complexity

Keywords
  • computational complexity theory
  • finite model theory
  • Boolean circuits
  • regular languages
  • finite monoids
  • Ehrenfeucht-Fraïssé-games