Publications (52)
Choiceless Polynomial Time with Witnessed Symmetric Choice
Moritz Lichter, Pascal Schweitzer
We extend Choiceless Polynomial Time (CPT), the currently only remaining promising candidate in the quest for a logic capturing PTime, so that this extended logic has the following…
Finite Variable Counting Logics with Restricted Requantification
Simon RaÃmann, Georg Schindling, Pascal Schweitzer
Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula…
Interval Graphs are Reconstructible
Irene Heinrich, Masashi Kiyomi, Yota Otachi +1
A graph is reconstructible if it is determined up to isomorphism by the multiset of its proper induced subgraphs. The reconstruction conjecture postulates that every graph of order…
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…
A Faster Isomorphism Test for Graphs of Small Degree
Martin Grohe, Daniel Neuen, Pascal Schweitzer
In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our a…
Classification of Finite Highly Regular Vertex-Coloured Graphs
Irene Heinrich, Thomas Schneider, Pascal Schweitzer
A coloured graph is k-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most k extends to an automorphism. A coloured graph is t-tuple regular if the…