Linear matroid intersection is in quasi-NC

DOI10.1145/3055399.3055440zbMath1370.68325OpenAlexW2625490399MaRDI QIDQ4978026

Rohit Gurjar, Thomas Thierauf

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3055399.3055440

zbMATH Keywords

derandomizationmatroid intersectionpolynomial identity testingisolation lemma

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Randomized algorithms (68W20)

Related Items (14)

Unnamed Item ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Linear matroid intersection is in quasi-NC ⋮ Unnamed Item ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Unnamed Item ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Improved hitting set for orbit of ROABPs ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

This page was built for publication: Linear matroid intersection is in quasi-NC