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:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6ad665221cc40
DTSTART;TZID=America/Toronto:20261023T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20261023T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-sepehr-assadi-greedy-optimal-semi-streaming
SUMMARY:Tutte Colloquium | Sepehr Assadi\, Greedy is Optimal for the\nSemi-
 Streaming Matching Problem
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n Sepehr Assadi\n\nAFFILIATION:\n University of Waterl
 oo\n\nLOCATION:\n MC 5501\n\nABSTRACT: We prove that no single-pass semi-s
 treaming algorithm\n(deterministic or randomized) can achieve a better-tha
 n-half\napproximation to the maximum matching problem. This implies the\no
 ptimality of the naive greedy algorithm\, answering a longstanding\nopen q
 uestion in graph streaming literature since the introduction of\nthe model
 . Our proof consists of two main parts:\n\n 1. Blueprint framework: reduc
 ing the problem of proving lower bounds\nfor semi-streaming matching to co
 nstructing certain combinatorial\nobjects which we call blueprints\; and\,
 \n\n 2. Blueprint construction: an optimal construction of such\nblueprin
 ts usable within this framework.\n\n Putting these two parts together imp
 lies our semi-streaming matching\nlower bound.\n\nBased on joint work with
  Max Jiang and Mars Xiang in\nhttps://arxiv.org/abs/2607.14644 (STOC 2026)
  and\nhttps://arxiv.org/abs/2607.14656 (arXiv\; July 2026)
DTSTAMP:20261019T184450Z
END:VEVENT
END:VCALENDAR