Computer Science Speakers Calendar

View Full Calendar

Taihei Oki "Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
3401 SC
Virtual
wifi event
Date
Feb 20, 2023   11:00 am  
Speaker
Taihei Oki, University of Tokyo
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
74

We look forward to seeing you in-person in 3401 SC or online on Monday, February 20 for the Theory Seminar. 

Abstract: Matrix representations are a powerful tool for designing efficient algorithms for combinatorial optimization problems such as matching, and linear matroid intersection and parity. In my talk, we initiate the study of matrix representations using the concept of non-commutative rank (nc-rank), which has recently attracted attention in the research of Edmonds' problem. We reveal that the nc-rank of the matrix representation of linear matroid parity corresponds to the optimal value of fractional linear matroid parity: a half-integral relaxation of linear matroid parity. Based on our representation, we present an algebraic algorithm for the fractional linear matroid parity problem by building a new technique to incorporate the search-to-decision reduction into the half-integral problem represented via the nc-rank. We further present a faster divide-and-conquer algorithm for finding a maximum fractional matroid matching and an algebraic algorithm for finding a dual optimal solution. Our algorithms are significantly simpler and faster than the existing algorithms. 

Joint work with Tasuku Soma (MIT). SODA '23  https://arxiv.org/abs/2207.07946

link for robots only