License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.5.9.105
URN: urn:nbn:de:0030-drops-56872
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5687/
Go back to Dagstuhl Reports

Bojanczyk, Mikolaj ; Mahajan, Meena ; Schwentick, Thomas ; Vollmer, Heribert
Weitere Beteiligte (Hrsg. etc.): Mikolaj Bojanczyk and Meena Mahajan and Thomas Schwentick and Heribert Vollmer

Circuits, Logic and Games (Dagstuhl Seminar 15401)

pdf-format:
dagrep_v005_i009_p105_s15401.pdf (1 MB)

Abstract

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 firstorder 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. 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

The seminar had 43 participants from 11 countries and was very successful with respect to the exchange of recent results, ideas and methodological approaches.

BibTeX - Entry

@Article{bojanczyk_et_al:DR:2016:5687,
  author =	{Mikolaj Bojanczyk and Meena Mahajan and Thomas Schwentick and Heribert Vollmer},
  title =	{{Circuits, Logic and Games (Dagstuhl Seminar 15401)}},
  pages =	{105--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{9},
  editor =	{Mikolaj Bojanczyk and Meena Mahajan and Thomas Schwentick and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5687},
  URN =		{urn:nbn:de:0030-drops-56872},
  doi =		{10.4230/DagRep.5.9.105},
  annote =	{Keywords: computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fraiss{\'e}-games}
}

Keywords: computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fraissé-games
Collection: Dagstuhl Reports, Volume 5, Issue 9
Issue Date: 2016
Date of publication: 21.01.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI