IMSc Webinar

A deterministic parallel reduction from the weighted linear matroid intersection search to decision

Sumanta Ghosh

California Institute of Technology

Online talk. To join,
zoom.us/j/99018916192?pwd=WE9IbmkrTlk5M20zZTRuVEpndlg3QT09
Meeting ID: 990 1891 6192
Passcode: 9Tv6Ej

Given two sets of m vectors each, the linear matroid intersection problem asks for a set of indices B, which is a subset of [m], that corresponds to a basis set in each of the two sets of vectors, and such a set B is called a common base. The weighted version of the problem asks for a common base with maximum weight. This problem generalizes the bipartite matching problem. The linear matroid intersection problem is known to have randomized parallel (RNC) algorithms, when the weights are polynomially bounded. Finding a deterministic parallel algorithm (NC) in this case, even for the decision question, has been a long-standing open question. In this talk, we present an NC algorithm for the weighted linear matroid intersection search problem using an oracle for its weighted decision version. In other words, our result shows that the weighted linear matroid intersection search problem is equivalent to its weighted decision version, in the parallel model of computation. This resolves an open question posed by Anari and Vazirani (ITCS 2020). The talk is based on joint work with Rohit Gurjar and Roshan Raj.