BARC talk by Joakim Blikstad

Wednesday, 18 May 2022, Joakim Blikstad, a PhD student at KTH Royal Institute of Technology in Stockholm, Sweden, will give a talk on "Sublinear-round Parallel Matroid Intersection".

Title:
Sublinear-round Parallel Matroid Intersection

Abstract:
Joakim Blikstad will present his ICALP'22 paper "Sublinear-round Parallel Matroid Intersection".

Matroid intersection is a fundamental combinatorial optimization problem which can model a range of important problems, e.g. bipartite matching or packing spanning-trees / arborescences. There has been a lot of recent progress in obtaining faster sequential matroid intersection algorithms. However, the fastest parallel algorithm was still, prior to this work, the over 50 years old O(n)-round parallel implementation of Edmonds' augmenting paths algorithm.

To beat this O(n)-round barrier we show how to find several “compatible” augmenting paths in parallel (which, for matroid intersection, turns out to be much trickier than for the related problems of bipartite-matching and maximum-flow). This leads to the first sublinear-round parallel matroid intersection algorithm, specifically taking O(n^(3/4))-rounds.

No background about matroid intersection is needed for the talk.

Bio:
Joakim Blikstad is a second-year Ph.D. student at KTH Royal Institute of Technology in Stockholm, advised by Danupon Na Nongkai. Previously he studied at University of Waterloo in Canada. His research interests are primarily in combinatorial optimization and algorithms: particularly about matroid intersection and related graph problems. Other than research, he loves to go skiing in the winters and sailing in the summers.