BARC talk by Joakim Blikstad

Wednesday, 25 July 2021, Joakim Blikstad, Ph.D. student at KTH Royal Institute of Technology in Stockholm, will give a talk on "Breaking the quadratic barrier for matroid intersection".

Title: 
Breaking the quadratic barrier for matroid intersection

Abstract:
Joakim Blikstad will present recent developments in matroid intersection algorithms. Matroid intersection is a fundamental combinatorial optimization problem which can model a range of problems, e.g. bipartite matching or packing spanning-trees / arborescences.
We obtain faster matroid intersection algorithms by studying a specific graph reachability problem, for which we show new and simple algorithms. The exact complexity of this reachability problem, however, remains open. Combining our graph reachability algorithms with recent approximation algorithms, we manage to obtain the first subquadratic matroid intersection algorithms, thus breaking the "quadratic barrier".

No background about matroid intersection is needed for the talk.

The talk is based on the STOC'21 paper "Breaking the Quadratic Barrier for Matroid Intersection", https://arxiv.org/abs/2102.05548. Joint work with Jan van den Brand, Sagnik Mukhopadhyay and Danupon Nanongkai.

Bio:
Joakim Blikstad is a first-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. He also enjoys doing competitive programming.