|
|
AbstractsINVITED TALKS
Albert Atserias (Universitat Politècnica de Catalunya) Title: Are Average-Case Lower Bounds for Symmetric Boolean Circuits Within Reach? Abstract: While proving impossibility results for general Boolean circuits is the holly grail of computational complexity theory, the progress in this area is, admittedly, very slow. The same question for restricted models of Boolean circuits has seen much more success: strong and close to optimal lower bounds are known for bounded-depth Boolean circuits with and without modular counting gates, monotone Boolean circuits, symmetric Boolean circuits with and without majority gates, among others. In this talk I will partially survey some of these results, with emphasis on the logic-based methods for symmetric Boolean circuits of various types, and discuss the prospects for proving average-case lower bounds (on Erdos-Renyi random graphs, say) for them.
Anuj Dawar (University of Cambridge) Title: Seese's conjecture: an update Abstract: Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. It remains open thirty years after it was first formulated. In this talk, I outline an approach to the conjecture based on classifying classes of unbounded clique-width.
Sebastian Siebertz (University of Bremen) Title: Algorithmic meta-theorems Abstract: Algorithmic meta-theorems provide general explanations when and why certain algorithmic problems can be solved efficiently. They are typically formulated in terms of logic (defining the descriptive complexity of the problems) and structural properties of their inputs. In this talk I will give an overview over the classical meta-theorems for first-order logic (FO) and monadic second-order logic (MSO) as well as recent results for logics with expressive power that lies between these two logics.
Szymon Toruńczyk (University of Warsaw) Title: On monadically stable and monadically NIP classes of graphs Abstract: Sparsity theory, initiated by Ossona de Mendez and Nesetril, identifies those classes of sparse graphs that are tractable in various ways (e. g. from the perspective of the model checking problem for first order logic) as exactly the nowhere dense classes. There is an ongoing effort aimed at generalizing sparsity theory to classes of graphs that are not necessarily sparse. It is conjectured that the relevant notion characterising dense graph classes that are tractable, generalising nowhere denseness, is the notion of monadically NIP classes, introduced by Shelah in model theory. I will survey some recent progress in the understanding of those classes, and of the related monadically stable classes. In particular, monadically NIP classes are a common generalization of the notions of nowhere denseness and of twin-width, introduced recently by Bonnet, Thomasse, and coauthors.
REGULAR TALKS
Zdeněk Dvořák (Computer Science Institute, Charles University) Title: Approximation meta-algorithms for FO properties Abstract: An important result of Grohe, Kreutzer, and Siebertz shows that all optimization problems expressible in the first-order logic (such as the independence number or domination number) are fixed-parameter tractable (when parameterized by the solution size) in graphs from a monotone graph class if and only if the class is nowhere dense, subject to standard complexity-theoretic assumptions. What about approximation algorithms for these problems? We survey the meta-algorithmic and complexity results on this topic and present some open questions.
Ioannis Eleftheriadis (University of Cambridge) Title: Monadic NIP in monotone classes of relational structures Abstract: It is conjectured that the hereditary classes of structures that admit fixed parameter tractable model-checking are precisely those that are (monadically) NIP. We provide a positive answer to this conjecture in the case of monotone classes of arbitrary relational structures. This is established by showing that (monadic) NIP coincides with having nowhere dense Gaifman class for monotone classes. Colin Geniet (Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP) Title: First-order logic and twin-width in tournaments
Lars Jaffke (Department of Informatics, University of Bergen) Title: A logic-based algorithmic meta-theorem for mim-width Abstract: We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MSO1 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions. Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length. Joint work with Benjamin Bergougnoux and Jan Dreier.
Stephan Kreutzer (TU Berlin) Title: Model Checking on Interpretations of Classes of Bounded Local Cliquewidth Abstract: We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and more generally, of classes of bounded genus. To obtain this result we develop a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future Joint work with Édouard Bonnet, Jan Dreier, Jakub Gajarský, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk.
Mamadou Kanté (LIMOS, CNRS, Aubière,) Title: MSOL-definability of decompositions Abstract: After recalling interest in definability of decompositions, I will show how to define in MSOL branch-decompositions for strongly pigeonhole matroids of bounded linear decomposition-width. Strongly pigeonhole matroids include finitely representable matroids, but also fundamental transversal matroids and 3-connected bi-circular ones. They are characterised by the following property : for each subset X, the number of equivalence classes wrt matroid circuit is bounded by the connectivity of X.
Matthieu Rosenfeld (LIRMM, Univ Montpellier) Title: Bounding the number of sets defined by a given MSO formula on trees
Peter Rossmanith (RWTH Aachen) Title: Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
Ignasi Sau (LIRMM, Univ Montpellier, CNRS) Title: Compound Logics for Modification Problems
Giannos Stamoulis (LIRMM, Univ Montpellier) Title: Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classe Joint work with Petr A. Golovach and Dimitrios M. Thilikos
Stefan Szeider (Algorithms and Complexity Group, Faculty of Informatics, TU Wien) Title: From Twin-Width to Propositional Logic and Back |
Online user: 1 | Privacy |