Logo Leibniz Universität Hannover
Logo: Theoretical Computer Science
Logo Leibniz Universität Hannover
Logo: Theoretical Computer Science
  • Zielgruppen
  • Suche

Circuits, Logic, and Games 07.02.10 - 12.02.10

Dagstuhl Seminar Page


Benjamin Rossmann MIT - Cambridge, USA
Thomas Schwentick U. Dortmund, DE
Denis Thérien McGill U. - Montreal, CA
Heribert Vollmer U. Hannover, DE

Description of the Seminar'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 computa-
tional model of Boolean circuits. Emerging powerful lower bound techniques
promised progress towards solutions of major open problems in computa-
tional 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.

During the first seminar on Circuits, Logic, and Games (Nov. 2006,
06451), the organizers aimed to bring together researchers from the areas
of nite model theory and computational complexity theory, since they felt
that perhaps not all developments in circuit theory and in logic had been ex-
plored fully in the context of lower bounds. In fact, the interaction between
the areas has nourished a lot in the past 2-3 years, as can be exemplied 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 suces to separate
such classes from NC^1 . 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

While inexpressibility results in finite model theory have been used since
the 1980s to obtain circuit lower bounds, recent results of Rossman make use
of circuit lower bounds to separate different logics : He concluded that the
number-of-variable hierarchy in rst-order logic over nite ordered structures
is strict by showing that the k -clique-problem (for graphs with n nodes) can-
not be solved by constant-depth circuits of size n^(1/4) . The circuit lower bound
makes use of the theory of random graphs and a game-theoretic argument.

Further connections between logic and circuits concern uniformity condi-
tions for Boolean circuits : Building on 20 year old results from Immerman et
al., Behle and Lange recently proved that in a quite general context, when
a circuit based language class is characterized using rst-order descriptive
complexity, the circuit uniformity conditions spring up in the logic in the
form of restrictions on the set of numerical predicates allowed. McKenzie,
Thomas, and Vollmer studied so called "extensional uniformity conditions":
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 rst-order logic with L-numerical predicates.
(Intuitively, L-numerical predicates are those predicates denable in rst-
order logic with one "oracle call" to a language from L, i. e., more precisely,
with one appearance of a generalized quantier for such a language.)

While this in principal points out new ways to separate uniformity con-
ditions via logical means, results of Allender, Barrington, and Hesse go in
the opposite direction: They show that for a specic arithmetical problem
(division), circuits can be constructed that are uniform under much stricter
requirements than was anticipated before. Again, their proofs make heavy
use of nite model theory.

Employing techniques from nite model theory in form of particular
Ehrenfeucht-Fraïssé games, new tools have been developed to obtain lower
bounds for the size of Boolean formulas (that is, circuits with fan-out 1)
and rst-order formulas. Adler and Immerman (and, unpublished, Hella
and Väänänen) dened EF games that characterize denability of classes
of structures with rst-order formulas of given size. Using these techniques,
Immerman and Weis obtained lower bounds for formulas with bounded num-
ber of variables and studied the trade-off between formula size and number
of variables. The game based techniques were also applied by Grohe and
Schweikardt who initiated a systematic study of different logics.

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^0 update complexity. Recent (and forthcoming)
work therefore started an investigation of the ne structure of the class of
problems with AC^0 updates, yielding lower bound results and uncovering
(yet another) surprising characterization of the regular languages as those
that can be maintained with quantier-free formulas.

These results demonstrate the impressive growth of interest and activity
in the intersection of nite model theory and Boolean circuit complexity, and
as will have become apparent from our above description of recent research,
many of these developments rely strongly on game-based methods.

It will be the aim of the workshop to bring together researchers from
these two areas to further strengthen the mutual fertilization.