Linear matroid intersection is in quasi-NC
From MaRDI portal
Publication:2027206
DOI10.1007/s00037-020-00200-zzbMath1468.90150OpenAlexW3109156225MaRDI QIDQ2027206
Publication date: 25 May 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-020-00200-z
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Parallel algorithms in computer science (68W10) Combinatorial aspects of matroids and geometric lattices (05B35) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On computing the determinant in small parallel time using a small number of processors
- Matching is as easy as matrix inversion
- The complexity of parallel search
- A probabilistic remark on algebraic program testing
- Maximum rank matrix completion
- Fast Parallel Computation of Polynomials Using Few Processors
- Matroid Intersection
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Singular spaces of matrices and their application in combinatorics
- Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
- Linear matroid intersection is in quasi-NC
- Bipartite perfect matching is in quasi-NC
- Deterministic Polynomial Time Algorithms for Matrix Completion Problems
- Systems of distinct representatives and linear algebra
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Linear matroid intersection is in quasi-NC
