Circuits, Logic and Games (Dagstuhl Seminar 15401)

Authors Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, Heribert Vollmer and all authors of the abstracts in this report



PDF
Thumbnail PDF

File

DagRep.5.9.105.pdf
  • Filesize: 1.09 MB
  • 20 pages

Document Identifiers

Author Details

Mikolaj Bojanczyk
Meena Mahajan
Thomas Schwentick
Heribert Vollmer
and all authors of the abstracts in this report

Cite AsGet BibTex

Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, and Heribert Vollmer. Circuits, Logic and Games (Dagstuhl Seminar 15401). In Dagstuhl Reports, Volume 5, Issue 9, pp. 105-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/DagRep.5.9.105

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.
Keywords
  • computational complexity theory
  • finite model theory
  • Boolean circuits
  • regular languages
  • finite monoids
  • Ehrenfeucht-Fraissé-games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail