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:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69d3cac12dc34
DTSTART;TZID=America/Toronto:20240927T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240927T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-eric-blais
SUMMARY:Tutte colloquium-Eric Blais
CLASS:PUBLIC
DESCRIPTION:Graph Property Testing using the Container Method\n\nSPEAKER:\n
  Eric Blais\n\nAFFILATION:\n University of Waterloo\n\nLOCATION:\n MC 5501
 \n\nABSTRACT: The Graph and Hypergraph Container Methods have recently\nbe
 en used to obtain multiple striking results across different areas\nof mat
 hematics. In this talk\, we will see how the graph container\nmethod is pa
 rticularly well-suited for the study of some fundamental\nproblems in grap
 h property testing.\n\nThe main problem we will discuss in the talk is the
  Independent Set\nTesting problem introduced by Goldreich\, Goldwasser\, a
 nd Ron (1998).\nIn this problem\, we are given oracle access to a graph on
  $n$ vertices\nthat either (i) contains an independent set on $\\rho n$ ve
 rtices\, or\n(ii) is $\\epsilon$-far from the property in the sense that a
 t least\n$\\epsilon n^2$ edges must be removed from the graph to make it h
 ave an\nindependent set of this size. We will introduce a new container le
 mma\nfor the latter class of graphs and we will show how this lemma can be
 \nused to obtain a near-optimal solution to the Independent Set Testing\np
 roblem. We will also discuss how variants and extensions of the new\nconta
 iner lemma can be used to prove a variety of other results in\nproperty te
 sting.\n\nThis is joint work with Cameron Seth.
DTSTAMP:20260406T150121Z
END:VEVENT
END:VCALENDAR