{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:32:38Z","timestamp":1724459558171},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,8,6]],"date-time":"2008-08-06T00:00:00Z","timestamp":1217980800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,1]]},"DOI":"10.1007\/s00224-008-9136-8","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T16:02:39Z","timestamp":1217952159000},"page":"9-26","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Matrix Rank and Rigidity"],"prefix":"10.1007","volume":"46","author":[{"given":"Meena","family":"Mahajan","sequence":"first","affiliation":[]},{"given":"Jayalal M. N.","family":"Sarma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,8,6]]},"reference":[{"key":"9136_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/3-540-48523-6_12","volume-title":"Proc. 26th ICALP","author":"E. Allender","year":"1999","unstructured":"Allender, E., Ambainis, A., Mix Barrington, D.A., Datta, S., LeThanh, H.: Bounded-depth arithmetic circuits: counting and closure. In: Proc. 26th ICALP. Lecture Notes in Computer Science, vol. 1644, pp. 149\u2013158. Springer, Berlin (1999)"},{"issue":"4","key":"9136_CR2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00224-003-1077-7","volume":"36","author":"E. Allender","year":"2003","unstructured":"Allender, E., Arvind, V., Mahajan, M.: Arithmetic complexity, Kleene closure, and formal power series. Theory Comput. Syst. 36(4), 303\u2013328 (2003)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9136_CR3","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s000370050023","volume":"8","author":"E. Allender","year":"1999","unstructured":"Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Comput. Complex. 8(2), 99\u2013126 (1999)","journal-title":"Comput. Complex."},{"key":"9136_CR4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/PL00001603","volume":"9","author":"C. \u00c0lvarez","year":"2000","unstructured":"\u00c0lvarez, C., Greenlaw, R.: A compendium of problems complete for symmetric logarithmic space. Comput. Complex., 9, 73\u201395 (2000)","journal-title":"Comput. Complex."},{"key":"9136_CR5","series-title":"Quaderni di Matematica","first-page":"33","volume-title":"Complexity of Computations and Proofs","author":"E. Allender","year":"2004","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Krajicek, J. (ed.) Complexity of Computations and Proofs. Quaderni di Matematica, vol. 13, pp. 33\u201372. Seconda Universita di Napoli, Napoli (2004)"},{"issue":"1","key":"9136_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, #l, and the determinant. RAIRO Theor. Inform. Appl. 30(1), 1\u201321 (1996)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9136_CR7","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and importance of logspace MOD-classes. Math. Syst. Theory 25, 223\u2013237 (1992)","journal-title":"Math. Syst. Theory"},{"key":"9136_CR8","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1006\/jcss.1998.1608","volume":"58","author":"J.F. Buss","year":"1999","unstructured":"Buss, J.F., Frandsen, G.S., Shallit, J.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58, 572\u2013596 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9136_CR9","series-title":"GTM","volume-title":"Modern Graph Theory","author":"B. Bollobas","year":"1984","unstructured":"Bollobas, B.: Modern Graph Theory. GTM, vol. 184. Springer, Berlin (1984)"},{"key":"9136_CR10","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S.A. Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for L. J.\u00a0Algorithms 8, 385\u2013394 (1987)","journal-title":"J.\u00a0Algorithms"},{"key":"9136_CR11","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic $\\textsf{NC}^{1}$ computation. J. Comput. Syst. Sci. 57, 200\u2013212 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9136_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0024-3795(00)00178-6","volume":"317","author":"G. Dahl","year":"1999","unstructured":"Dahl, G.: A note on nonnegative diagonally dominant matrices. Linear Algebra Appl. 317, 217\u2013224 (1999)","journal-title":"Linear Algebra Appl."},{"key":"9136_CR13","unstructured":"Damm, C.: DET\u2009=\u2009L(#L). Technical Report Informatik-Preprint 8, Fachbereich Informatik der Humboldt\u2013Universit\u00e4t zu Berlin (1991)"},{"key":"9136_CR14","unstructured":"Deshpande, A.: Sampling-based dimension reduction algorithms. PhD thesis, MIT, May 2007"},{"issue":"1\u20133","key":"9136_CR15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0024-3795(98)10210-0","volume":"288","author":"J.F. Geelen","year":"1999","unstructured":"Geelen, J.F.: Maximum rank matrix completion. Linear Algebra Appl. 288(1\u20133), 211\u2013217 (1999)","journal-title":"Linear Algebra Appl."},{"key":"9136_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9136_CR17","series-title":"Notes of the Leningrad Branch of the Steklov Mathematical Institute","volume-title":"Using the Notions of Separability and Independence for Proving the Lower Bounds on the Circuit Complexity","author":"D.Y. Grigoriev","year":"1976","unstructured":"Grigoriev, D.Y.: Using the Notions of Separability and Independence for Proving the Lower Bounds on the Circuit Complexity. Notes of the Leningrad Branch of the Steklov Mathematical Institute. Nauka, Moscow (1976) (in Russian)"},{"key":"9136_CR18","unstructured":"Kulkarni, R.: Personal communication, January 2007"},{"key":"9136_CR19","first-page":"221","volume-title":"The Encyclopedia of Optimization","author":"M. Laurent","year":"2001","unstructured":"Laurent, M.: Matrix completion problems. In: Floudas, C.A., Pardalos, P.M. (eds.) The Encyclopedia of Optimization, vol. 3, pp. 221\u2013229. Kluwer, Dordrecht (2001)"},{"key":"9136_CR20","unstructured":"Lokam, S.V.: Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity. In: Proc. 36th FOCS, pp. 6\u201315, 1995; J. Comput. Syst. Sci. 63(3):449\u2013473 (2001)"},{"key":"9136_CR21","series-title":"The Prindle, Weber and Schmidt Complementary Series in Mathematics","volume-title":"A Survey of Matrix Theory and Matrix inequalities","author":"M. Marcus","year":"1964","unstructured":"Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix inequalities. The Prindle, Weber and Schmidt Complementary Series in Mathematics, vol. 14. Allyn and Bacon, Boston (1964)"},{"key":"9136_CR22","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02579205","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K.: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7, 101\u2013104 (1987)","journal-title":"Combinatorica"},{"key":"9136_CR23","series-title":"The IMA Volumes in Mathematics and Its Applications","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-1-4613-8354-3_2","volume-title":"Combinatorial and Graph-Theoretic Problems in Linear Algebra","author":"K. Murota","year":"1993","unstructured":"Murota, K.: Mixed matrices\u2014irreducibility and decomposition. In: Brualdi, R.A., Friedland, S., Klee, V. (eds.) Combinatorial and Graph-Theoretic Problems in Linear Algebra. The IMA Volumes in Mathematics and Its Applications, vol. 50, pp. 39\u201371. Springer, Berlin (1993)"},{"key":"9136_CR24","unstructured":"Mahajan, M., Vinay, V.: Determinant: combinatorics, algorithms, complexity. Chic. J. Theor. Comput. Sci. 5 (1997)"},{"key":"9136_CR25","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ta-Shma, A.: Symmetric logspace is closed under complement. Chic. J. Theor. Comput. Sci., (1995).","DOI":"10.4086\/cjtcs.1995.001"},{"key":"9136_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01213466","volume":"6","author":"S. Poljak","year":"1993","unstructured":"Poljak, S., Rohn, J.: Checking robust nonsingularity is $\\textsf {NP}$ -hard. Math. Control Signals Syst. 6, 1\u20139 (1993)","journal-title":"Math. Control Signals Syst."},{"key":"9136_CR27","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected st-conenctivity in logspace. In Proc. 37th STOC, pp. 376\u2013385 (2005).","DOI":"10.1145\/1060590.1060647"},{"key":"9136_CR28","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0024-3795(89)90004-9","volume":"126","author":"J. Rohn","year":"1989","unstructured":"Rohn, J.: Systems of linear interval equations. Linear Algebra Appl. 126, 39\u201378 (1989)","journal-title":"Linear Algebra Appl."},{"key":"9136_CR29","first-page":"795","volume":"35","author":"J. Rohn","year":"1994","unstructured":"Rohn, J.: Checking positive definiteness or stability of symmetric interval matrices is NP-hard. Comment. Math. Univ. Carol. 35, 795\u2013797 (1994)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"1","key":"9136_CR30","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9136_CR31","unstructured":"Toda, S.: Counting problems computationally equivalent to the determinant. Technical Report CSIM 91-07, Dept. of Comput. Sci. & Information Mathematics, Univ of Electro-Communications, Chofu-shi, Tokyo (1991)"},{"key":"9136_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-08353-7_135","volume-title":"Proc. 6th MFCS","author":"L.G. Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph theoretic arguments in low-level complexity. In: Proc. 6th MFCS. Lecture Notes in Computer Science, vol.\u00a053, pp. 162\u2013176. Springer, Berlin (1977)"},{"key":"9136_CR33","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1017\/CBO9780511526633.008","volume-title":"Proceedings of the London Mathematical Society symposium on Boolean function complexity","author":"L.G. Valiant","year":"1992","unstructured":"Valiant, L.G.: Why is Boolean complexity theory difficult? In: Proceedings of the London Mathematical Society symposium on Boolean function complexity, pp. 84\u201394. Cambridge University Press, New York (1992)"},{"key":"9136_CR34","series-title":"Lecture Notes in Computer Science","first-page":"270","volume-title":"Proc. 6th Structure in Complexity Theory Conference","author":"V. Vinay","year":"1991","unstructured":"Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In: Proc. 6th Structure in Complexity Theory Conference. Lecture Notes in Computer Science, vol. 223, pp. 270\u2013284. Springer, Berlin (1991)"},{"key":"9136_CR35","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, Berlin (1999)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9136-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9136-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9136-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:36Z","timestamp":1558698696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9136-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,6]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["9136"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9136-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,6]]}}}