Dagstuhl Seminar 15401
Circuits, Logic and Games
( Sep 27 – Oct 02, 2015 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/15401
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)
Contact
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits: article in "Logic, Language, Information, and Computation" : pp 234-248 - Haak, Anselm; Vollmer, Heribert - Berlin : Springer, 2016 - Lecture notes in computer science ; 9803 : article).
- Descriptive Complexity of #AC0 Functions : article in Computer Science Logic 2016, CSL 2016 - Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert - Wadern : LZI, 2016. - pp. 1-16 - (Leibniz International Proceedings in Informatics ; 62 : article).
- Two-variable Logic with a Between Relation : article in LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science : pp. 106-115 - Krebs, Andreas; Lodaya, Kamal; Pandya, Paritosh K.; Straubing, Howard - New York : ACM, 2016 - (Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science ; article).
Schedule
The interplay between circuit complexity and logic is notoriously fruitful: for example, 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 growth of interest and activity in the intersection of finite model theory and Boolean circuit complexity. It will be the aim of the seminar to bring together researchers from these two areas to further strengthen the mutual fertilisation.
Specific topics that the seminar will cover are:
- 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: unerstanding the dynamic expressive power of small depth circuit classes
A main goal of the seminar is to work towards complexity-theoretic lower bounds for Boolean circuits, obtained by methods from logic or finite model theory, in particular games.
We hope that the seminar can have a similar impact as the previous Dagstuhl seminars on this topic, by bringing the communities together again to discuss how methods from one area can be fruitfully applied in the other area.
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.
Creative Commons BY 3.0 Unported license
Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, and Heribert Vollmer
- Sreejith Ajithkumar (University of Paris VII, FR)
- Christoph Berkholz (HU Berlin, DE) [dblp]
- Olaf Beyersdorff (University of Leeds, GB) [dblp]
- Mikolaj Bojanczyk (University of Warsaw, PL) [dblp]
- Michaël Cadilhac (Universität Tübingen, DE) [dblp]
- Thomas Colcombet (CNRS / University Paris-Diderot, FR) [dblp]
- Aiswarya Cyriac (Uppsala University, SE) [dblp]
- Samir Datta (Chennai Mathematical Institute, IN) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Michael Elberfeld (RWTH Aachen, DE) [dblp]
- Martin Grohe (RWTH Aachen, DE) [dblp]
- Rohit Gurjar (Universität Ulm, DE) [dblp]
- Anselm Haak (Leibniz Universität Hannover, DE) [dblp]
- Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
- Jan Johannsen (LMU München, DE) [dblp]
- Juha Kontinen (University of Helsinki, FI) [dblp]
- Andreas Krebs (Universität Tübingen, DE) [dblp]
- Klaus-Jörn Lange (Universität Tübingen, DE) [dblp]
- Nutan Limaye (Indian Institute of Technology - Mumbai, IN) [dblp]
- Kamal Lodaya (The Institute of Mathematical Sciences, IN) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Arne Meier (Leibniz Universität Hannover, DE) [dblp]
- Stefan Mengel (CNRS, CRIL - Lens, FR) [dblp]
- David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
- Anish Mukherjee (Chennai Mathematical Institute, IN) [dblp]
- Anca Muscholl (University of Bordeaux, FR) [dblp]
- Charles Paperman (University of Warsaw, PL) [dblp]
- Jean-Eric Pin (University of Paris VII, FR) [dblp]
- Raghavendra Rao B.V. (Indian Institute of Techology - Madras, IN) [dblp]
- Thomas Schwentick (TU Dortmund, DE) [dblp]
- Luc Segoufin (ENS - Cachan, FR) [dblp]
- Sebastian Siebertz (TU Berlin, DE) [dblp]
- Karteek Sreenivasaiah (MPI für Informatik - Saarbrücken, DE) [dblp]
- Howard Straubing (Boston College, US) [dblp]
- Dimitri Surinx (Hasselt University - Diepenbeek, BE) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Jan Van den Bussche (Hasselt University - Diepenbeek, BE) [dblp]
- Jonni Virtema (Leibniz Universität Hannover, DE) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Nils Vortmeier (TU Dortmund, DE) [dblp]
- Thomas Zeume (TU Dortmund, DE) [dblp]
Related Seminars
Classification
- data structures / algorithms / complexity
Keywords
- computational complexity theory
- finite model theory
- Boolean circuits
- regular languages
- finite monoids
- Ehrenfeucht-Fraisse-games
