research
∙
09/09/2023
Descriptive complexity of controllable graphs
Let G be a graph on n vertices with adjacency matrix A, and let 1 be the...
share
research
∙
08/07/2023
Quantifiers closed under partial polymorphisms
We study Lindstrom quantifiers that satisfy certain closure properties w...
research
∙
02/11/2023
Monadic NIP in monotone classes of relational structures
We prove that for any monotone class of finite relational structures, th...
research
∙
10/11/2022
Descriptive complexity of the generalized spectra of graphs
Two graphs are cospectral if their respective adjacency matrices have th...
research
∙
09/15/2021
Limitations of the Invertible-Map Equivalences
This note draws conclusions that arise by combining two recent papers, b...
research
∙
07/23/2021
Lower Bounds for Symmetric Circuits for the Determinant
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithm...
research
∙
07/12/2021
Separating LREC from LFP
LREC= is an extension of first-order logic with a logarithmic recursion ...
research
∙
05/07/2021
Lovász-Type Theorems and Game Comonads
Lovász (1967) showed that two finite relational structures A and B are i...
research
∙
03/30/2021
On the relative power of algebraic approximations of graph isomorphism
We compare the capabilities of two approaches to approximating graph iso...
research
∙
11/05/2020
MSO Undecidability for some Hereditary Classes of Unbounded Clique-Width
Seese's conjecture for finite graphs states that monadic second-order lo...
research
∙
07/10/2020
Extension Preservation in the Finite and Prefix Classes of First Order Logic
It is well known that the classic Łoś-Tarski preservation theorem fails ...
research
∙
06/29/2020
Game Comonads Generalised Quantifiers
Game comonads, introduced by Abramsky, Dawar and Wang and developed by A...
research
∙
02/15/2020
Symmetric Arithmetic Circuits
We introduce symmetric arithmetic circuits, i.e. arithmetic circuits wit...
research
∙
02/10/2020
Relativization of Gurevich's Conjectures
Gurevich (1988) conjectured that there is no logic for P or for NP∩coNP....
research
∙
06/03/2019
Generalizations of k-Weisfeiler-Leman partitions and related graph invariants
The family of Weisfeiler-Leman equivalences on graphs is a widely studie...
research
∙
02/18/2019
Approximations of Isomorphism and Logics with Linear-Algebraic Operators
Invertible map equivalences are approximations of graph isomorphism that...
research
∙
01/23/2019
On the Power of Symmetric Linear Programs
We consider families of symmetric linear programs (LPs) that decide a pr...
research
∙
09/21/2018
Constructing Hard Examples for Graph Isomorphism
We describe a method for generating graphs that provide difficult exampl...
research
∙
06/29/2018
Definable Inapproximability: New Challenges for Duplicator
We consider the hardness of approximation of optimization problems from ...
research
∙
04/09/2018