Computer Science/Discrete Mathematics Seminar I

In this talk, I'll discuss a recent result where we settle the complexities of the maximum-cardinality bipartite 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].  We also settle the communication complexity of the generalizations of BMM, such as maximum-cost bipartite b-matching and transshipment; and the query complexity of unique bipartite perfect matching (answering an open question by Beniamini [2022]).  Our algorithms and lower bounds follow from simple applications of known techniques such as cutting planes methods and set disjointness.  Lastly, I'll discuss some cool open problems!

Based on joint work with Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay & Danupon Nanongkai from FOCS 2022.