Linear Matroid Intersection is in Quasi-NC
Linear Matroid Intersection is in Quasi-NC
复制标题
线性拟阵交集处于准数控状态
DOI：
10.1145/3055399.3055440
复制
发表时间：
2017
影响因子：
1.4
通讯作者：
Thomas Thierauf
中科院分区：
文献类型：
--
作者：
Rohit Gurjar;Thomas Thierauf
给定同一基集上的两个拟阵，拟阵交集问题要求找到一个最大尺寸的公共独立集。证明了线性拟阵的交问题是拟NC2的。也就是说，它具有拟多项式大小为O(Logn)，深度为Ando(Log2n)的均匀回路。这推广了二部完美匹配问题的类似结果。我们通过对拟阵交的隔离引理的一个几乎完全的去随机化来实现这一点，我们的结果还包含了形式为A0+A1z1+A2z2+…的符号矩阵的黑盒奇性检验+AMZM，其中A0是任意矩阵，并且矩阵A1、A2、…，在某一域上排名1的Amare。
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 sizenO(logn), andO(log2n) 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 formA0+A1z1+A2z2+ …+Amzm, whereA0is an arbitrary matrix and the matricesA1,A2,…,Amare of rank 1 over some field.
登录
查看更多内容
并行搜索的复杂性
DOI：
--
发表时间：
1988
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
R. Karp;E. Upfal;A. Wigderson
通讯作者：
A. Wigderson
拟阵交集
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
J. Edmonds
通讯作者：
J. Edmonds
矩阵补全问题的确定性多项式时间算法
DOI：
10.1112/s1461157013000296
发表时间：
2009
期刊：
LMS J. Comput. Math.
影响因子：
--
作者：
G. Ivanyos;Marek Karpinski;Nitin Saxena
通讯作者：
Nitin Saxena
准NC中的二分完美匹配
DOI：
10.1145/2897518.2897564
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf
影响因子：
64.8
作者：
M. Sansalone;N. Carino;N. Hsu
通讯作者：
M. Sansalone;N. Carino;N. Hsu