A Deterministic PTAS for the Commutative Rank of Matrix Spaces

by Markus Bläser, Gorav Jindal, and Anurag Pandey

Theory of Computing, Volume 14(3), pp. 1-21, 2018

Bibliography with links to cited articles

[1]   Markus Bläser, Gorav Jindal, and Anurag Pandey: Greedy strikes again: A deterministic PTAS for commutative rank of matrix spaces. In Proc. 32nd Computational Complexity Conf. (CCC’17), volume 79 of LIPIcs, pp. 33:1–33:16. DROPS, 2017. [doi:10.4230/LIPIcs.CCC.2017.33]

[2]   Jonathan F. Buss, Gudmund Skovbjerg Frandsen, and Jeffrey O. Shallit: The computational complexity of some problems of linear algebra. J. Comput. System Sci., 58(3):572–596, 1999. Preliminary version in STACS’97. [doi:10.1006/jcss.1998.1608]

[3]   Harm Derksen and Visu Makam: On non-commutative rank and tensor rank. Linear and Multilinear Algebra, pp. 1–16, 2017. [doi:10.1080/03081087.2017.1337058, arXiv:1606.06701]

[4]   Jack R. Edmonds: Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B, 71(4):241–245, 1967. [doi:10.6028/jres.071B.033]

[5]   David Eisenbud and Joe Harris: Vector spaces of matrices of low rank. Advances in Mathematics, 70(2):135–155, 1988. [doi:10.1016/0001-8708(88)90054-0]

[6]   Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf: Bipartite perfect matching is in quasi-NC. In Proc. 48th STOC, pp. 754–763. ACM Press, 2016. [doi:10.1145/2897518.2897564, arXiv:1601.06319]

[7]   Marc Fortin and Christophe Reutenauer: Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank. Séminaire Lotharingien de Combinatoire, 52:B52f, 2004. Available from EuDML.

[8]   Harold N. Gabow and Matthias F. M. Stallmann: An augmenting path algorithm for linear matroid parity. Combinatorica, 6(2):123–150, 1986. Preliminary version in FOCS’84. [doi:10.1007/BF02579169]

[9]   Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson: A deterministic polynomial time algorithm for non-commutative rational identity testing. In Proc. 57th FOCS, pp. 109–117. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.95, arXiv:1511.03730]

[10]   Rohit Gurjar and Thomas Thierauf: Linear matroid intersection is in quasi-NC. In Proc. 49th STOC, pp. 821–830. ACM Press, 2017. [doi:10.1145/3055399.3055440]

[11]   Leonid Gurvits: Classical complexity and quantum entanglement. J. Comput. System Sci., 69(3):448–484, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.06.003]

[12]   Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha: Generalized Wong sequences and their applications to Edmonds’ problems. J. Comput. System Sci., 81(7):1373–1386, 2015. Preliminary version in STACS’14. [doi:10.1016/j.jcss.2015.04.006, arXiv:1307.6429]

[13]   Gábor Ivanyos, Marek Karpinski, and Nitin Saxena: Deterministic polynomial time algorithms for matrix completion problems. SIAM J. Comput., 39(8):3736–3751, 2010. [doi:10.1137/090781231, arXiv:0907.0774]

[14]   Gábor Ivanyos, Youming Qiao, and K. Venkata Subrahmanyam: Constructive noncommutative rank computation in deterministic polynomial time, 2015-2018. [arXiv:1512.03531]

[15]   László Lovász: On determinants, matchings, and random algorithms. In Proc. 2nd Internat. Conf. Fundamentals of Computation Theory (FCT’79), pp. 565–574, 1979.

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

[17]   László Lovász and Michael D. Plummer: Matching Theory. Volume 367. AMS Chelsea Publ., 2009.

[18]   Meena Mahajan and V. Vinay: Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci., (5), 1997. [doi:10.4086/cjtcs.1997.005]

[19]    James B. Orlin: A fast, simpler algorithm for the matroid parity problem. In Proc. 13th Internat. Conf. on Integer Programming and Combinatorial Optimization (IPCO’08), volume 5035 of Lecture Notes in Comp. Sci., pp. 240–258. Springer, 2008. [doi:10.1007/978-3-540-68891-4_17]

[20]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. Preliminary version in EUROSAM’79. [doi:10.1145/322217.322225]

[21]   F. Bruce Shepherd and Adrian Vetta: The demand-matching problem. Math. Oper. Res., 32(3):563–578, 2007. Preliminary version in IPCO’02. [doi:10.1287/moor.1070.0254]

[22]   Seinosuke Toda: Counting problems computationally equivalent to computing the determinant. Technical Report CSIM 91-07, 1991.

[23]   Leslie G. Valiant: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM Press, 1979. [doi:10.1145/800135.804419]

[24]   V. Vinay: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proc. 6th IEEE Conf. on Structure in Complexity Theory (SCT’91), pp. 270–284. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SCT.1991.160269]

[25]   Richard Zippel: Probabilistic algorithms for sparse polynomials. In Proc. Symbolic and Algebraic Comput. (EUROSAM’79), volume 72 of Lecture Notes in Comp. Sci., pp. 216–226. Springer, 1979. [doi:10.1007/3-540-09519-5_73]