Query Lower Bounds for Matroids via Group Representations

Опубликовано 6 сентября 2016, 16:56

Finding an common independent set in two matroids is one of the classical problems of combinatorial optimization, including the well-known bipartite matching problem as a special case. In the early 1970s, algorithms for this problem were discovered that use O(n^3) queries for matroids on n elements. In Welsh's 1976 text on matroid theory, he asked the question of whether these algorithms are optimal. In the following thirty years, no non-trivial lower bounds were found. In this talk, I will present the first lower bound for this problem. We show that (log_2 3)*n queries are necessary for certain matroids. The arguments are based on communication complexity and representation theory of the symmetric group.