https://www.dagstuhl.de/15401

### September 27 – October 2 , 2015, Dagstuhl Seminar 15401

# Circuits, Logic and Games

## Organizers

Mikolaj Bojanczyk (University of Warsaw, PL)

Meena Mahajan (The Institute of Mathematical Sciences, IN)

Thomas Schwentick (TU Dortmund, DE)

Heribert Vollmer (Leibniz Universität Hannover, DE)

## For support, please contact

## Documents

Dagstuhl Report, Volume 5, Issue 9

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Schedule [pdf]

## Summary

This report documents the programme and outcomes of Dagstuhl Seminar 15401 "Circuits, Logic and Games". This seminar was the third in this series, the earlier two being Dagstuhl Seminars 06451 in November 2006 and 10061 in February 2010.

### Goals of the Seminar

Over the years, there has been a lot of interplay between circuit complexity and logic. There are tight connections between small-depth circuit classes and fragments and extensions of first-order logic, and ideas from games and finite model theory have provided powerful lower bound techniques for circuits.

In recent years, there has been an impressive and sustained growth of interest and activity in the intersection of finite model theory and Boolean circuit complexity. The central aim of the seminar was to bring together researchers from these two areas to further strengthen the mutual fertilisation. Given the ubiquitousness of algebraic techniques in circuit complexity, the seminar also included arithmetic circuit complexity in its ambit.

The seminar focussed on the following specific topics:

- The algebraic approach to circuit complexity with its applications to finite model theory
- The logic-circuit connection, with a particular emphasis on circuit lower bounds that trigger results in finite model theory like separations between logics
- New connections between uniformity conditions on circuit families and logical predicates
- Structural complexity and circuit lower bounds inherently using methods from logic and algebra
- Proof systems with low circuit complexity
- Dynamic complexity: understanding the dynamic expressive power of small depth circuit classes

### Organization of the Seminar and Activities

The seminar had the participation of 43 members from 11 countries.

The organisers attempted to create a schedule with a judicious mix of survey talks, focussed talks, and free time for unstructured discussions. Participants were invited to present their work and to communicate state-of-the-art advances. Since the participants came from diverse communities, the organisers invited some of them to give long survey-style talks in specific sub-areas. There were five such talks, listed below.

- Olaf Beyersdorff. Lower bounds: from circuits to QBF proof systems.

This talk surveyed the relatively new area of proof systems for establishing falseness of fully quantified Boolean formulas. It demonstrated techniques by which lower bounds in ciruit complexity can be tranferred to lower bounds on the sizes of such proofs. - Thomas Colcombet. Combinatorial Expressions and Lower Bounds.

This talk described an elegant formalism, combinatorial expressions, that captures bounded depth circuits manipulating infinite data in specified restrictive ways, and showed how one may obtain indefinability results in this model. - Anuj Dawar. Lower Bounds for Symmetric Circuits.

This talk described the recently formalised circuit model of symmetric circuits, its connections with logical definability, and a lower bound technique using games. - Martin Grohe. Color Refinement: A Simple Partitioning Algorithm
with Applications From Graph Isomorphism Testing to Machine
Learning.

This talk described exciting connections between higher-dimensional generalisations of the extremely simple colour refinement aglorithm and a linear programming approach to testing isomorphism. - Nutan Limaye. Arithmetic Circuit Lower Bounds.

This talk surveyed the recent explosion of results concerning size lower bounds in restricted models of algebraic computation, using techniques which seem essentially combinatorial in nature.

In addition, 20 other participants gave short talks on some of their recent work relevant to the seminar theme. These talks covered results in two-variable first-order logic; dynamic complexity; graph colouring; database theory; circuit lower bounds; logics on words; and semigroup techniques. There was also a short session on Thursday devoted to discussing interesting open problems.

### Concluding Remarks and Future Plans

The organizers regard the seminar as being quite successful. Most participants felt that they learnt new things from other areas, and were hopeful of using such ideas to make progress in their own research areas.

One aspect noted by the organizers was that a lot of the work discussed at the seminar used techniques from algebra. In fact, there was even a suggestion that if there is a future seminar in this series, it could be called "Circuits, Logic, and Algebra" instead of "Circuits, Logic, and Games".

The organizers are grateful to the Scientific Directorate of the Center for its support of this seminar.

**Summary text license**

Creative Commons BY 3.0 Unported license

Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, and Heribert Vollmer

## Dagstuhl Seminar Series

- 10061: "Circuits, Logic, and Games" (2010)
- 06451: "Circuits, Logic, and Games " (2006)

## Classification

- Data Structures / Algorithms / Complexity

## Keywords

- Computational complexity theory
- Finite model theory
- Boolean circuits
- Regular languages
- Finite monoids
- Ehrenfeucht-Fraisse-games