# Circuits, Logic, and Games 07.02.10 - 12.02.10

## Organizers

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

complexity

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.