VLDB 2026 Research / 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
| 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 |