Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-182 | 14th November 2016 16:14

#### Linear Matroid Intersection is in quasi-NC

TR16-182
Authors: Rohit Gurjar, Thomas Thierauf
Publication: 15th November 2016 22:38
Downloads: 266
Keywords:

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-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\$.

ISSN 1433-8092 | Imprint