TR16-182 Authors: Rohit Gurjar, Thomas Thierauf

Publication: 15th November 2016 22:38

Downloads: 394

Keywords:

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-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 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 $A_0+A_1 z_1 +A_2 z_2+ \cdots+A_m z_m$, where the matrices $A_1,A_2,\dots,A_m$ are of rank $1$.