Linear matroid intersection is in quasi-NC
type: Item
instance of: scholarly article
title: Linear matroid intersection is in quasi-NC
zbMATH Open document ID: 1468.90150
author: Rohit Gurjar
author: Thomas Thierauf
published in: Computational Complexity
publication date: 2021-05-25T00:00:00Z
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 7350837
zbMATH Keywords: matroid intersection
zbMATH Keywords: isolation lemma
zbMATH Keywords: derandomization
zbMATH Keywords: polynomial identity testing
MaRDI profile type: Publication
full work available at URL: s00037-020-00200-z
OpenAlex ID: W3109156225
cites work: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
cites work: On computing the determinant in small parallel time using a small number of processors
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: A probabilistic remark on algebraic program testing
cites work: Systems of distinct representatives and linear algebra
cites work: Q5593828
cites work: Q5684698
cites work: Matroid Intersection
cites work: Bipartite perfect matching is in quasi-NC
cites work: Storing a Sparse Table with 0 (1) Worst Case Access Time
cites work: Maximum rank matrix completion
cites work: Linear matroid intersection is in quasi-NC
cites work: Deterministic Polynomial Time Algorithms for Matrix Completion Problems
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: The complexity of parallel search
cites work: Singular spaces of matrices and their application in combinatorics
cites work: Matching is as easy as matrix inversion
cites work: Q4281309
cites work: Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Fast Parallel Computation of Polynomials Using Few Processors
cites work: Q3851616
DOI: 10.1007/S00037-020-00200-Z
description: scientific article; zbMATH DE number 7350837