Demo Data from EDBT 2026 / reviewers in the wild / expert
Johanna Brunar
dblp:398/4752
· DBLP profile ↗
2ranked-venue papers
2as first author
2since 2021 · last 2026
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 first-author · 2 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Computational complexity · 33% Graph algorithms and graph theory · 33% Logic in computer science · 33% |
Topics — the 6 heaviest of 6, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › constraint satisfaction › complexity classification
constraint satisfaction complexity |
0.9 | 1 | 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems · LICS 2025 |
Graph algorithms and graph theory › graph coloring
digraph coloring |
0.9 | 1 | 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems · LICS 2025 |
Graph algorithms and graph theory
graph coloring |
0.9 | 1 | 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems · LICS 2025 |
Computational complexity › constraint satisfaction
infinite-domain constraint satisfaction |
0.9 | 1 | 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems · LICS 2025 |
Logic in computer science
model theory |
0.9 | 1 | 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems · LICS 2025 |
Logic in computer science › model theory
omega-categorical structure |
0.9 | 1 | 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems · LICS 2025 |
Methods — techniques the papers use, named apart from their topics
pp-constructions · 0.9oligomorphic automorphism groups · 0.9algebraic length · 0.9
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | When Darwin Met Ianus: Dichotomies of Expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi |
MFCS | 1 |
| 2025 | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problemsabstractTwo major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov’s proof of the dichotomy for conservative templates, and the structural dichotomy for smooth digraphs of algebraic length 1 due to Barto, Kozik, and Niven. We lift the combined scenario to the infinite, and prove that any smooth digraph of algebraic length 1 pp-constructs, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, every finite structure – and hence its conservative graph-colouring problem is NP-hard – unless the digraph has a pseudo-loop, i.e. an edge within an orbit. We thereby overcome, for the first time, previous obstacles to lifting structural results for digraphs in this context from finite to ω-categorical structures; the strongest lifting results hitherto not going beyond a genera-lisation of the Hell-Nešetřil theorem for undirected graphs. As a consequence, we obtain a new algebraic invariant of arbitrary ω-categorical structures enriched by pairs of orbits which fail to pp-construct some finite structure. Johanna Brunar, Marcin Kozik, Tomás Nagy 0001, Michael Pinsker |
LICS | 1 |