11 citations · 21 across the 7 of their papers we have counts for
14 papers
Bounding the Weisfeiler-Leman Dimension via a Depth Analysis of I/R-Trees
Sandra Kiefer, Daniel Neuen
The Weisfeiler-Leman (WL) dimension is an established measure for the inherent descriptive complexity of graphs and relational structures. It corresponds to the number of variables…
Simulating Logspace-Recursion with Logarithmic Quantifier Depth
Steffen van Bergerem, Martin Grohe, Sandra Kiefer +1
The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in the quest for a logic to capture all problems decidable in logarithmic space. It extends FO+C, first-order l…
Refutations of pebble minimization via output languages
Sandra Kiefer, Lê Thành Dũng Nguyên, Cécilia Pradic
Polyregular functions are the class of string-to-string functions definable by pebble transducers, an extension of finite-state automata with outputs and multiple two-way reading h…
A Study of Weisfeiler-Leman Colorings on Planar Graphs
Sandra Kiefer, Daniel Neuen
The Weisfeiler-Leman (WL) algorithm is a combinatorial procedure that computes colorings on graphs, which can often be used to detect their (non-)isomorphism. Particularly the 1- a…
SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks
Christopher Morris, Gaurav Rattan, Sandra Kiefer +1
While (message-passing) graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs or general relational data, more expressive, hig…
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs and it is widely used in graph-isomorphism tests. It proceeds by iter…
The Iteration Number of Colour Refinement
Sandra Kiefer, Brendan D. McKay
The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem.…
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
Sandra Kiefer, Daniel Neuen
The Weisfeiler-Leman procedure is a widely-used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Mean…
String-to-String Interpretations with Polynomial-Size Output
Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of jus…
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism te…
The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
Sandra Kiefer, Ilia Ponomarenko, Pascal Schweitzer
We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic…
-SAT problem and its applications in dominating set problems
Arash Ahadi, Ali Dehghan
The satisfiability problem is known to be -complete in general and for many restricted cases. One way to restrict instances of -SAT is to limit the number of times…
Graphs Identified by Logics with Counting
Sandra Kiefer, Pascal Schweitzer, Erkal Selman
We classify graphs and, more generally, finite relational structures that are identified by C2, that is, two-variable first-order logic with counting. Using this classification, we…