BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260418T091013Z
UID:Seminar-dept-1312@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260310T130000
DTEND:20260310T140000
SUMMARY:School Seminar Series
DESCRIPTION:Liana Khazaliya: Non-Clashing Teaching in Graphs\n\nNon-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.\n\n\n\nIn 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.\n\n\n\nJoint work with Sujoy Bhore and Fionn Mc Inerney\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1312
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR