[日時] 2023年6月30日(金) 12:20--13:20
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 相馬 輔 (統計数理研究所)
[題目(Title)] Noncommutative rank and combinatorial optimization
[概要(Abstract)] Linear symbolic matrices naturally appear in combinatorial optimization and theoretical computer science. For example, computing the rank of linear symbolic matrices in deterministic polynomial time is a major open problem called Edmonds' problem. A recent breakthrough shows that one can compute the noncommutative rank (nc-rank) in deterministic polynomial time. In this talk, I present some of the recent results regarding nc-rank and combinatorial optimization. The first part discusses how to find a "shrunk subspace" (dual certificate of nc-rank) via a simple iterative method based on the Sinkhorn algorithm. The second part describes how nc-rank can be used to devise a simple algebraic algorithm for fractional linear matroid parity. The first part is based on a joint work with Cole Franks and Michel Goemans and the second part is with Taihei Oki.