BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20250309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cf7b6f23c45
DTSTART;TZID=America/Toronto:20250318T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20250318T160000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/graphs-and-m
 atroids-lior-gishboliner
SUMMARY:Graphs and Matroids - Lior Gishboliner
CLASS:PUBLIC
DESCRIPTION:TITLE:New results on the complexity of edge-modification proble
 ms\n\nSPEAKER:\n Lior Gishboliner\n\nAFFILIATION:\n University of Toronto\
 n\nLOCATION:\n MC 5479\n\nABSTRACT: \n\nFor a k-uniform hypergraph H\, the
  H-freeness edge modification problem\nis the algorithmic problem of findi
 ng\, for a given k-uniform input G\,\nthe distance of G from H-freeness\, 
 i.e.\, the minimum number of edges\nthat need to be deleted from G in orde
 r to obtain an H-free\nhypergraph. I will present new results on the compu
 tational complexity\nof this general problem. In particular\, I will show 
 that if H is not\nk-partite\, then it is NP-hard to compute the distance t
 o\nH-freeness\, and even to approximate this distance up to an additive\
 nerror of n^{k-delta} for any fixed delta > 0. This resolves a special\nca
 se of a problem raised by Ailon and Alon.\n\nThis is a joint work with Y
 evgeny Levanzov and Asaf Shapira.
DTSTAMP:20260403T083351Z
END:VEVENT
END:VCALENDAR