{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T03:55:23Z","timestamp":1792727723527,"version":"4.5.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T00:00:00Z","timestamp":1610496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61373002"],"award-info":[{"award-number":["61373002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over\n            <jats:italic>GF<\/jats:italic>\n            (2) in Hrube\u0161-Tzameret [15]. Specifically, we show that the multiplicativity of the determinant function and the Cayley-Hamilton theorem over the integers are provable in the bounded arithmetic theory\n            <jats:bold>VNC<\/jats:bold>\n            <jats:sup>2<\/jats:sup>\n            ; the latter is a first-order theory corresponding to the complexity class\n            <jats:bold>NC<\/jats:bold>\n            <jats:sup>2<\/jats:sup>\n            consisting of problems solvable by uniform families of polynomial-size circuits and\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-depth. This also establishes the existence of uniform polynomial-size propositional proofs operating with\n            <jats:bold>NC<\/jats:bold>\n            <jats:sup>2<\/jats:sup>\n            -circuits of the basic determinant identities over the integers (previous propositional proofs hold only over the two-element field).\n          <\/jats:p>","DOI":"10.1145\/3431922","type":"journal-article","created":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T17:12:14Z","timestamp":1610557934000},"page":"1-80","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Uniform, Integral, and Feasible Proofs for the Determinant Identities"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5558-9911","authenticated-orcid":false,"given":"Iddo","family":"Tzameret","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen A.","family":"Cook","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,13]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Eric Allender. 2018. Personal com  Eric Allender. 2018. Personal com"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00227-2"},{"key":"e_1_2_1_3_1","first-page":"66","article-title":"Propositional proof complexity: Past, present, and future","volume":"65","author":"Beame Paul","year":"1998","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_2_1_5_1","volume-title":"II(Progress in Computer Science and Applied Logic","volume":"56","author":"Bonet Maria Luisa","year":"1995"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102796"},{"key":"e_1_2_1_7_1","unstructured":"Samuel R. Buss. 1986. Bounded Arithmetic (Studies in Proof Theory Vol. 3). Bibliopolis.  Samuel R. Buss. 1986. Bounded Arithmetic (Studies in Proof Theory Vol. 3). Bibliopolis."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2015-06233-3"},{"key":"e_1_2_1_9_1","volume-title":"Logical Foundations of Proof Complexity. ASL Perspectives in Logic","author":"Cook Stephen"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803756"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_12_1","volume-title":"Fontes","author":"Cook Stephen A.","year":"2012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"P. H\u00e1jek and P. Pudl\u00e1k. 1993. Metamathematics of First-order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag Berlin.  P. H\u00e1jek and P. Pudl\u00e1k. 1993. Metamathematics of First-order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-662-22156-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/130917788"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2010.10.002"},{"key":"e_1_2_1_19_1","volume-title":"Propositional Logic, and Complexity Theory(Encyclopedia of Mathematics and its Applications","author":"Kraj\u00ed\u010dek Jan"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217044"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.08.001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.48"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269958"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"J. Paris and A. Wilkie. 1985. Counting problems in bounded arithmetic. In Methods in Mathematical Logic (Caracas 1983)(Lecture Notes in Mathematics Vol. 1130). Springer Berlin 317--340.  J. Paris and A. Wilkie. 1985. Counting problems in bounded arithmetic. In Methods in Mathematical Logic (Caracas 1983)(Lecture Notes in Mathematics Vol. 1130). Springer Berlin 317--340.","DOI":"10.1007\/BFb0075316"},{"key":"e_1_2_1_26_1","volume-title":"Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic. Log. Meth. Comput. Sci. 11, 2","author":"Pich J\u00e1n","year":"2015"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984450.2984455"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0254-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_30_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_31_1","volume-title":"Subsystems of Second Order Arithmetic","author":"Simpson Stephen"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.10.018"},{"key":"e_1_2_1_34_1","first-page":"182","article-title":"Vermeidung von divisionen","volume":"264","author":"Strassen Volker","year":"1973","journal-title":"J. Reine Angew. Math."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-004-0249-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1991.160269"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431922","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3431922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:31Z","timestamp":1750195891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,13]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3431922"],"URL":"https:\/\/doi.org\/10.1145\/3431922","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,13]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}