The next TCS+ talk will take place this coming Wednesday, September 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Joakim Blikstad from KTH Stockholm will speak about “Nearly Optimal Communication and Query Complexity of Bipartite Matching” (abstract below).
You can reserve a spot as an individual or a group to join us live by signing up on the online form. 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 recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: With a simple application of the cutting planes method, we settle the complexities of the bipartite maximum matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC’88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS’12; Dobzinski, Nisan, and Oren STOC’14; Nisan SODA’21] and tighten the lower bounds shown by Beniamini and Nisan [STOC’21] and Zhang [ICALP’04]. Our communication protocols also work for some generalizations of BMM, such as maximum-cost bipartite b-matching and transshipment, using only Õ(|V|) bits of communications.
To appear in FOCS’22. Joint work with Jan van den Brand, Yuval Efron, Danupon Nanongkai, and Sagnik Mukhopadhyay. preprint: https://arxiv.org/abs/2208.02526