[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Linear Matroid Intersection is in Quasi-NC

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. In case of linear matroids, the problem had a randomized parallel algorithm but no deterministic one. We give an almost complete derandomization of this algorithm, which implies that the linear matroid intersection problem is in quasi-NC. That is, it has uniform circuits of quasi-polynomial size \(n^{O(\log n)}\) and O(polylog(n)) depth. Moreover, the depth of the circuit can be reduced to O(log2 n) in case of zero characteristic fields. This generalizes a similar result for the bipartite perfect matching problem. Our main technical contribution is to derandomize the Isolation lemma for the family of common bases of two matroids. We use our isolation result to give a quasi-polynomial time blackbox algorithm for a special case of Edmonds' problem, i.e., singularity testing of a symbolic matrix, when the given matrix is of the form \(A_{0} + A_{1 }x_{1} + \cdots + A_{m} x_{m}\), for an arbitrary matrix A0 and rank-1 matrices \(A_{1}, A_{2}, \dots, A_{m}\). This can also be viewed as a blackbox polynomial identity testing algorithm for the corresponding determinant polynomial. Another consequence of this result is a deterministic solution to the maximum rank matrix completion problem. Finally, we use our result to find a deterministic representation for the union of linear matroids in quasi-NC.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Manindra Agrawal (2005). Proving Lower Bounds Via Pseudo-random Generators. In FSTTCS, volume 3821 of Lecture Notes in Computer Science, 92–105.

  • Matthew Anderson, Amir Shpilka & Ben Lee Volk (2016). Personal communication.

  • David A. Mix Barrington (1992). Quasipolynomial Size Circuit Classes. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 86–93. http://dx.doi.org/10.1109/SCT.1992.215383.

  • Stuart J. Berkowitz (1984). On computing the determinant in small parallel time using a small number of processors. Information Processing Letters 18(3), 147–150. ISSN 0020-0190.

  • Allan Borodin, Stephen Cook & Nicholas Pippenger (1984). Parallel Computation for Well-endowed Rings and Space-bounded Probabilistic Machines. Information and Control 58(1-3), 113–136. ISSN 0019-9958.

  • Richard A. Demillo & Richard J. Lipton (1978). A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193–195. ISSN 0020-0190.

  • Edmonds, Jack: Systems of distinct representatives and linear algebra. Journal of research of the National Bureau of Standards 71, 241–245, 1967

    Article  MathSciNet  Google Scholar 

  • Edmonds, Jack: Matroid partition. Mathematics of the Decision Sciences 11, 335–345, 1968

    MathSciNet  MATH  Google Scholar 

  • Edmonds, Jack: Submodular Functions, Matroids, and Certain Polyhedra. Combinatorial Structures and Their Applications, pp. 69–87. Gordon and Breach, New York 1970

    Google Scholar 

  • Jack Edmonds (1979). Matroid Intersection. In Discrete Optimization I (Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium), E.L. Johnson P.L. Hammer & B.H. Korte, editors, volume 4, 39–49. Elsevier. http://www.sciencedirect.com/science/article/pii/S0167506008708173.

  • Stephen Fenner, Rohit Gurjar & Thomas Thierauf (2019). Bipartite Perfect Matching is in Quasi-NC. SIAM Journal on Computing 0(0), STOC16–218–STOC16–235. https://doi.org/10.1137/16M1097870.

  • Stephen A. Fenner, Rohit Gurjar & Thomas Thierauf (2016). Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 754–763.

  • Michael A. Forbes (2014). Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph.D. thesis, MIT.

  • Michael L. Fredman, János Komlós & Endre Szemerédi (1984). Storing a Sparse Table with \(O(1)\) Worst Case Access Time. J. ACM 31(3), 538–544. ISSN 0004-5411. http://doi.acm.org/10.1145/828.1884.

  • James F. Geelen (1999). Maximum rank matrix completion. Linear Algebra and its Applications 288, 211–217. ISSN 0024-3795. http://www.sciencedirect.com/science/article/pii/S0024379598102100.

  • Rohit Gurjar & Thomas Thierauf (2017). Linear Matroid Intersection is in quasi-NC. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC: 821–830. ACM, New York, NY, USA 2017. ISBN 978-1-4503-4528-6

    Google Scholar 

  • Rohit Gurjar, Thomas Thierauf & Nisheeth K. Vishnoi (2017). Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. CoRR abs/1708.02222. http://arxiv.org/abs/1708.02222.

  • G‚bor Ivanyos, Marek Karpinski & Nitin Saxena, , : Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal of computing 39(8), 2010, 2010

  • Valentine Kabanets & Russell Impagliazzo (2003). Derandomizing polynomial identity tests means proving circuit lower bounds. STOC 355–364.

  • Richard M. Karp, Eli Upfal & Avi Wigderson (1988). The complexity of parallel search. Journal of Computer and System Sciences 36(2), 225–253. ISSN 0022-0000. http://www.sciencedirect.com/science/article/pii/002200008890027X.

  • László Lovász (1985). Computing ears and branchings in parallel. 26th Annual Symposium on Foundations of Computer Science (SFCS 1985) 464–467.

  • László Lovász (1989). Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática - Bulletin/Brazilian Mathematical Society 20(1), 87–99. ISSN 1678-7714. http://dx.doi.org/10.1007/BF02585470.

  • Ketan Mulmuley, Umesh V. Vazirani & Vijay V. Vazirani (1987). Matching is as easy as matrix inversion. Combinatorica 7, 105–113. ISSN 0209-9683. http://dx.doi.org/10.1007/BF02579206.

  • Murota, Kazuo: Mixed Matrices: Irreducibility and Decomposition. In: Brualdi, Richard A., Friedland, Shmuel, Klee, Victor (eds.) Combinatorial and Graph-Theoretical Problems in Linear Algebra, pp. 39–71. Springer, New York, New York, NY 1993. ISBN 978-1-4613-8354-3. http://dx.doi.org/10.1007/978-1-4613-8354-3_2

  • H. Narayanan, Huzur Saran & Vijay V. Vazirani (1994). Randomized Parallel Algorithms for Matroid Union and Intersection, With Applications to Arboresences and Edge-Disjoint Spanning Trees. SIAM J. Comput. 23(2), 387–397. http://dx.doi.org/10.1137/S0097539791195245.

  • Oxley, James G.: Matroid Theory (Oxford Graduate Texts in Mathematics). Oxford University Press Inc, New York, NY, USA 2006. ISBN 0199202508

  • Alexander Schrijver (2003). Combinatorial optimization : polyhedra and efficiency. Vol. B. , Matroids, trees, stable sets. chapters 39-69. Algorithms and combinatorics. Springer-Verlag, Berlin, Heidelberg, New York, N.Y., et al. ISBN 3-540-44389-4. http://opac.inria.fr/record=b1124843.

  • Schwartz, Jacob T.: Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM 27(4), 701–717, 1980

    Article  MathSciNet  Google Scholar 

  • L. G. Valiant (1979). Completeness Classes in Algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, 249–261. ACM, New York, NY, USA. http://doi.acm.org/10.1145/800135.804419.

  • L. G. Valiant, S. Skyum, S. Berkowitz & C. Rackoff (1983). Fast parallel computation of polynomials using few processors. SIAM journal of computing 12(4), 641–644. ISSN 0097-5397 (print), 1095-7111 (electronic).

  • Richard Zippel (1979). Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (EUROSAM), 216–226. Springer-Verlag. ISBN 3-540-09519-5.

Download references

Acknowledgements

This work is supported by DFG grant TH 472/4 and TH 472/5. Part of the work was done during Dagstuhl Seminar 16411 on Algebraic Methods in Computational Complexity 2016. A preliminary version of this work appeared in the proceedings of 49th Annual ACM Symposium on the Theory of Computing (STOC) 2017 (Gurjar & Thierauf 2017).

We are thankful to Matthew Anderson, Amir Shpilka and Ben Lee Volk for letting us use their reduction (Lemma 4.3). We would like to thank Stephen Fenner, Ankit Gupta, Jacobo Tóran, Ben Lee Volk, and Magnus Wahlström for helpful discussions. We thank the anonymous referees for many useful suggestions.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, MH, 400076, India

    Rohit Gurjar

  2. Faculty of Electronics and Computer Science, Aalen University, 73430, Aalen, Germany

    Thomas Thierauf

Authors
  1. Rohit Gurjar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Thierauf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rohit Gurjar .

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gurjar , R., Thierauf, T. Linear Matroid Intersection is in Quasi-NC. comput. complex. 29, 9 (2020). https://doi.org/10.1007/s00037-020-00200-z

Download citation

  • Received:

  • Published:

  • DOI: https://doi.org/10.1007/s00037-020-00200-z

Keywords

Subject classification

Search

Navigation