Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-182 | 14th November 2016 16:14

Linear Matroid Intersection is in quasi-NC

RSS-Feed




TR16-182
Authors: Rohit Gurjar, Thomas Thierauf
Publication: 15th November 2016 22:38
Downloads: 394
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