ECCC-Report TR16-182https://eccc.weizmann.ac.il/report/2016/182Comments and Revisions published for TR16-182en-usTue, 15 Nov 2016 22:38:57 +0200
Paper TR16-182
| Linear Matroid Intersection is in quasi-NC |
Rohit Gurjar,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/2016/182Given 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$.
Tue, 15 Nov 2016 22:38:57 +0200https://eccc.weizmann.ac.il/report/2016/182