TCS+ talk: Wednesday, September 30, Sepehr Assadi, University of Waterloo
Clement Canonne
Our next talk will take place this coming Wednesday, September 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Sepehr Assadi from University of Waterloo will tell us how "Greedy is Optimal for the Semi-Streaming Matching Problem" (abstract below).
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Sepehr Assadi (University of Waterloo)
Title: Greedy is Optimal for the Semi-Streaming Matching Problem
Abstract: We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering a longstanding open question in graph streaming literature since the introduction of the model. Our proof consists of two main parts:
1. Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and,
2. Blueprint construction: an optimal construction of such blueprints usable within this framework.
Putting these two parts together implies our semi-streaming matching lower bound.
Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/abs/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, September 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Sepehr Assadi (University of Waterloo)
Title: Greedy is Optimal for the Semi-Streaming Matching Problem
Abstract: We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering a longstanding open question in graph streaming literature since the introduction of the model. Our proof consists of two main parts:
1. Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and,
2. Blueprint construction: an optimal construction of such blueprints usable within this framework.
Putting these two parts together implies our semi-streaming matching lower bound.
Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/abs/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>
Sent: Friday, September 25, 2026 7:00 AM
To: TCS+ Announcement Mailing List
Subject: TCS+ talk: Wednesday, September 30, Sepehr Assadi, University of Waterloo
You received this message because you are subscribed to the Google Groups "TCS+" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus_announ...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/tcsplus_announce/SY4PR01MB7240F15696...@SY4PR01MB7240.ausprd01.prod.outlook.com.
For more options, visit https://groups.google.com/d/optout.
Clement Canonne
The link for tomorrow's TCS+ talk (first of the season!) has been posted: you will be able to join tomorrow (Wednesday), starting at 12:50pm ET: https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
(you will need to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>