Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Johanna Brunar

dblp:398/4752 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Computational complexity › constraint satisfaction › complexity classification
constraint satisfaction complexity
0.912025
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.912025
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.912025
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.912025
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.912025
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.912025
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
YearPublicationVenuePosition
2026 When Darwin Met Ianus: Dichotomies of Expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
MFCS1
2025 The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
abstract
Two 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
LICS1