Rohit Gurjar, Thomas Thierauf
Abstract:
Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of
maximum size.
We show that the linear matroid intersection problem is in quasi-NC2.
That is, it has uniform circuits of quasi-polynomial size nO(log n),
and O(log2 n) depth.
This generalizes the similar result for the bipartite perfect matching problem.
We do this by an almost complete derandomization of the Isolation lemma for matroid intersection.
Our result also implies a
blackbox singularity test for symbolic matrices of the form
A0 + A1 z1 + A2 z2 + ... + Am zm , where the matrices A1, A2, ...,Am are of rank 1.