{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:44Z","timestamp":1725489164776},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540002253"},{"type":"electronic","value":"9783540362067"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36206-1_19","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T03:23:08Z","timestamp":1187234588000},"page":"206-217","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of the Inertia"],"prefix":"10.1007","author":[{"given":"Thanh Minh","family":"Hoang","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,12,16]]},"reference":[{"key":"19_CR1","unstructured":"E. Allender, V Arvind, and M. Mahajan. Arithmetic complexity, Kleene closure, and formal power series, 1999."},{"key":"19_CR2","unstructured":"E. Allender and M. Ben-Or. Electronic Communication, 2001."},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s000370050023","volume":"8","author":"E. Allender","year":"1999","unstructured":"E. Allender, R. Beals, and M. Ogihara. The complexity of matrix rank and feasible systems of linear equations. Computational Complexity, 8:99\u2013126, 1999.","journal-title":"Computational Complexity"},{"key":"19_CR4","unstructured":"E. Allender. Personal Communication, 2002."},{"key":"19_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"E. Allender and M. Ogihara. Relationship among PL, #L, and the determinant. RAIRO-Theoretical Informatics and Applications, 30:1\u201321, 1996.","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"S. Berkowitz","year":"1984","unstructured":"S. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18:147\u2013150, 1984.","journal-title":"Information Processing Letters"},{"key":"19_CR7","unstructured":"C. Damm. DET = L(#L). Technical Report Informatik-Preprint 8, Fachbereich Informatik der Humboldt Universitaet zu Berlin, 1991."},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48:116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"S. Fortune. Exact computation of the inertia of symmetric integer matrices. In 32th Symposium on Theory of Computing, STOC 2000, pages 556\u2013564. ACM Press, 2000.","DOI":"10.1145\/335305.335374"},{"key":"19_CR10","unstructured":"F. Gantmacher. The Theory of Matrices, volume 1 and 2. AMS Chelsea Publishing, 1977."},{"key":"19_CR11","unstructured":"A. Graham. Kronnecker Products and Matrix Calculus: With Applications. Ellis Horwood Ltd., 1981."},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1985.","DOI":"10.1017\/CBO9780511810817"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"R. Horn and C. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991.","DOI":"10.1017\/CBO9780511840371"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"T. M. Hoang and T. Thierauf. The complexity of verifying the characteristic polynomial and testing similarity. In 15th IEEE Conference on Computational Complexity (CCC), pages 87\u201395. IEEE Computer Society Press, 2000.","DOI":"10.1109\/CCC.2000.856738"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"T. M. Hoang and T. Thierauf. The complexity of the minimal polynomial. In 26th International Symposium, MFCS 2001, pages 408\u2013420. Springer, 2001.","DOI":"10.1007\/3-540-44683-4_36"},{"key":"19_CR16","unstructured":"T. M. Hoang and T. Thierauf. The complexity of the characteristic and the minimal polynomial. Invited paper to the special issue in Theoretical Computer Scienceof the 26th MFCS conference 2001, to appear, 2002."},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"D. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1991.","DOI":"10.1007\/978-1-4612-4400-4"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/S0022-0000(05)80061-3","volume":"48","author":"C. A. Neff","year":"1994","unstructured":"C. A. Neff. Specified precision root isolation is in NC. Journal of Computer and System Science, 48:429\u2013463, 1994.","journal-title":"Journal of Computer and System Science"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1006\/jcom.1996.0008","volume":"12","author":"C. A. Neff","year":"1996","unstructured":"C. A. Neff and J. H. Reif. An efficient algorithm for the complex roots problem. Journal of Complexity, 12:81\u2013115, 1996.","journal-title":"Journal of Complexity"},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1137\/S0097539795295924","volume":"27","author":"M. Ogihara","year":"1998","unstructured":"M. Ogihara. The PL hierarchy collapses. SIAM Journal on Computing, 27:1430\u20131437, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/PL00001596","volume":"7","author":"M. Santha","year":"1998","unstructured":"M. Santha and S. Tan. Verifying the determinant in parallel. Computational Complexity, 7:128\u2013151, 1998.","journal-title":"Computational Complexity"},{"key":"19_CR22","unstructured":"S. Toda. Counting problems computationally equivalent to the determinant. Technical Report CSIM 91-07, Dept. of Computer Science and Information Mathematics, University of Electro-Communications, Chofu-shi, Tokyo 182, Japan, 1991."},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8:410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"L. Valiant. Why is Boolean complexity theory difficult. In M.S. Paterson, editor, Boolean Function Complexity, London Mathematical Society Lecture Notes Series 169. Cambridge University Press, 1992.","DOI":"10.1017\/CBO9780511526633.008"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"V Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In 6th IEEE Conference on Structure in Complexity Theory, pages 270\u2013284, 1991.","DOI":"10.1109\/SCT.1991.160269"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36206-1_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:08:15Z","timestamp":1556755695000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36206-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540002253","9783540362067"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-36206-1_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}