40 citations · 45 across the 4 of their papers we have counts for
5 papers
Some remarks on the uncolored versions of the original CFI-graphs
Yijia Chen, Jörg Flum, Mingjun Liu
The CFI-graphs, named after Cai, Fürer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are colored graphs, and…
On Algorithms Based on Finitely Many Homomorphism Counts
Yijia Chen, Jörg Flum, Mingjun Liu +1
It is well known [Lovász, 67] that up to isomorphism a graph~ is determined by the homomorphism counts , i.e., the number of homomorphisms from to , where …
Slicewise definability in first-order logic with bounded quantifier rank
Yijia Chen, Joerg Flum, Xuangui Huang
For every let denote the class of sentences of first-order logic FO of quantifier rank at most . If a graph property can be defined in $\textrm{…
Model-Checking Problems as a Basis for Parameterized Intractability
Joerg Flum, Martin Grohe
Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For exa…
Fixed-parameter tractability, definability, and model checking
Joerg Flum, Martin Grohe
In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized m…