Non-Clashing Teaching in Graphs

10^th March 2026, 13:00 Ashton Lecture Theatre
Liana Khazaliya
TU Wien

Abstract

Non-clashing teaching, introduced by Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023], is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark of Goldman and Mathias [COLT 1993]. In the past few years, (positive) non-clashing teaching for the concept class of balls in graphs has been thoroughly studied, yielding numerous algorithmic and combinatorial results. This concept class also exhibits broad generality, as any finite binary concept class can be equivalently represented by a set of closed neighborhoods in a graph.

In this talk, I will survey the complexity landscape of non-clashing teaching in graphs. I will present some of our recent results, including near-tight running time upper and lower bounds for general graphs, parameterized algorithmic and hardness results, and combinatorial bounds for broader graph classes.

Joint work with Sujoy Bhore and Fionn Mc Inerney

Additional Materials

• https://arxiv.org/pdf/2602.00657