10061 Abstracts Collection - Circuits, Logic, and Games

Benjamin Rossman, Thomas Schwentick, Denis Thérien, Heribert Vollmer

TL;DR

This document is a collection of abstracts from the Dagstuhl Seminar 10061, "Circuits, Logic, and Games." It showcases cutting-edge research at the intersection of computational complexity, finite model theory, and formal logic, highlighting new results and open problems in areas like proof complexity, parameterized complexity, and circuit complexity.

What Problem Does This Paper Address?

The seminar and this collection of abstracts address the fundamental challenge of understanding the computational power and limitations of various logical systems and their relationship to circuit complexity. Specifically, researchers are exploring how to prove lower bounds for computational problems, understand the complexity of reasoning in different logical frameworks, and characterize the expressive power of logical languages in terms of computational models like circuits and automata. The overarching goal is to bridge the gap between theoretical computer science and logic, fostering new insights and techniques.

Methods

The methods employed are diverse, reflecting the interdisciplinary nature of the seminar. They include:

  • Proof Complexity Techniques: Developing and analyzing sequent calculi, and establishing lower bounds on proof sizes for propositional default logic.
  • Parameterized Complexity: Introducing new combinatorial approaches and games (Prover-Delayer games) to analyze the complexity of problems with respect to a parameter, particularly in the context of resolution.
  • Circuit Complexity Analysis: Investigating exact threshold circuits, uniform and non-uniform circuit classes, and their relationships to other complexity classes like AC⁰ and CC⁰.
  • Logical Characterizations: Using logical frameworks, including dependence logic, modal dependence logic, and addition-invariant first-order logic, to characterize computational complexity classes and properties of formal languages.
  • Dynamic Complexity: Studying how problems can be maintained under updates, leading to new characterizations of regular languages and separations of complexity classes.
  • Algebraic Methods: Employing tools from algebraic automata theory to connect logical expressiveness with properties of monoids and regular languages.

Datasets

Not discussed in the paper. This document is a collection of research abstracts, not an empirical study with datasets.

Key Insights and Ideas

  • Interplay between Logic and Circuits: The seminar highlights the deep and fruitful connections between different areas of logic and circuit complexity, suggesting that progress in one area can often lead to breakthroughs in another.
  • New Tools for Lower Bounds: The development of novel games and combinatorial techniques (like Prover-Delayer games) offers promising new avenues for proving lower bounds in proof complexity and parameterized complexity.
  • Characterizing Complexity Classes: Researchers are making significant progress in logically characterizing various complexity classes, providing a deeper understanding of their structure and relationships.
  • Understanding Trade-offs: The work on parameterized resolution and probabilistic circuits demonstrates how introducing parameters or randomness can impact computational power and lead to new equivalences or separations between complexity classes.
  • Expressiveness of Logical Fragments: Investigating fragments of logics, such as modal dependence logic, reveals how even minor restrictions can drastically alter computational complexity, leading to complete classifications.

Key Results

  • Proof Complexity: Exponential lower bounds for skeptical default reasoning in a specific calculus are established.
  • Parameterized Resolution: New combinatorial approaches are devised to obtain lower bounds for tree-like Parameterized Resolution, and it's shown that dag-like Parameterized Resolution is not fpt-bounded.
  • Circuit Complexity: A new characterization of ACC⁰ is provided using constant width planar nondeterministic branching programs. It's also shown that the AND function can be computed by uniform probabilistic CC circuits using only O(logn) random bits.
  • Dependence Logic: Open formulas of dependence logic are shown to correspond to the negative fragment of existential second-order logic.
  • Modal Dependence Logic: The satisfiability problem for various fragments of modal dependence logic is completely classified, ranging from NEXPTIME-complete to PSPACE-complete and second-level polynomial hierarchy complete.
  • Addition-Invariant FO: A characterization of regular languages definable in addition-invariant first-order logic is given, and it's shown that certain bounded or context-free languages are regular.
  • Dynamic Complexity: Languages maintainable in DynPROP are shown to be exactly the regular languages, leading to separations of DynPROP from DynQF and DynFO.

Limitations and Future Work

  • Open Problems: The paper implicitly points to many open problems, such as the challenge of providing explicit super-polynomial lower bounds for depth two threshold circuits.
  • Derandomization: The work on probabilistic circuits suggests that derandomization could lead to significant collapses of circuit classes (e.g., ACC⁰ = CC⁰), indicating a clear direction for future research.
  • Generalizing Techniques: The success of new games and logical characterizations suggests that these techniques can be further developed and applied to a wider range of problems and complexity classes.
  • Understanding Trade-offs: Further exploration of the trade-offs between different logical operators, parameters, and computational models is a promising avenue for future work.

Summary updated

Abstract

From 07/02/10 to 12/02/10, the Dagstuhl Seminar 10061 ``Circuits, Logic, and Games '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
BibTeX
@inproceedings{rossman2010abstracts,
  author = {Benjamin Rossman and Thomas Schwentick and Denis Thérien and Heribert Vollmer},
  title = {{10061 Abstracts Collection - Circuits, Logic, and Games}},
  booktitle = {Circuits, Logic, and Games},
  year = {2010},
  url = {https://openreview.net/forum?id=xVB3wKj6AJ},
}
Figure