{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:06Z","timestamp":1784110326079,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":20,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993703","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"499-508","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Almost settling the hardness of noncommutative determinant"],"prefix":"10.1145","author":[{"given":"Steve","family":"Chien","sequence":"first","affiliation":[{"name":"Google, Mountain View, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prahladh","family":"Harsha","sequence":"additional","affiliation":[{"name":"TIFR, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[{"name":"University of California Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806782"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1%3C29::AID-RSA2%3E3.0.CO;2-X"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00010-2"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447359"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/647892.739605"},{"key":"e_1_3_2_2_8_1","volume-title":"Representation Theory of Finite Groups and Associative Algebras. No. XI in Pure and Applied Mathematics","author":"Curtis C. W.","year":"1962","unstructured":"Curtis , C. W. , and Reiner , I . Representation Theory of Finite Groups and Associative Algebras. No. XI in Pure and Applied Mathematics . Interscience Publishers , 1962 . Curtis, C. W., and Reiner, I. Representation Theory of Finite Groups and Associative Algebras. No. XI in Pure and Applied Mathematics. Interscience Publishers, 1962."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002000050066"},{"key":"e_1_3_2_2_10_1","first-page":"241","volume-title":"Algebraic Methods in Graph Theory","author":"Godsil C. D.","year":"1981","unstructured":"Godsil , C. D. , and Gutman , I . On the matching polynomial of a graph . In Algebraic Methods in Graph Theory , Vol. I , L. Lov\u00e1sz and V. T. S'os, Eds. North Holland, Amsterdam-New York , 1981 , pp. 241 -- 249 . Godsil, C. D., and Gutman, I. On the matching polynomial of a graph. In Algebraic Methods in Graph Theory, Vol. I, L. Lov\u00e1sz and V. T. S'os, Eds. North Holland, Amsterdam-New York, 1981, pp. 241--249."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.31"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222021"},{"key":"e_1_3_2_2_13_1","series-title":"Graduate texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-0406-7","volume-title":"A first course in noncommutative rings","author":"Lam T.-Y.","year":"1991","unstructured":"Lam , T.-Y. A first course in noncommutative rings , vol. 131 of Graduate texts in Mathematics . Springer , 1991 . Lam, T.-Y. A first course in noncommutative rings, vol. 131 of Graduate texts in Mathematics. Springer, 1991."},{"key":"e_1_3_2_2_14_1","article-title":"Determinant: Combinatorics, algorithms, and complexity","volume":"5","author":"Mahajan M.","year":"1997","unstructured":"Mahajan , M. , and Vinay , V . Determinant: Combinatorics, algorithms, and complexity . Chicago J. Theor. Comput. Sci . 1997 , 5 (1997). (Preliminary version in 8th SODA, 1997). Mahajan, M., and Vinay, V. Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci. 1997, 5 (1997). (Preliminary version in 8th SODA, 1997).","journal-title":"Chicago J. Theor. Comput. Sci"},{"key":"e_1_3_2_2_15_1","volume-title":"Approximating the permanent via nonabelian determinants","author":"Moore C.","year":"2009","unstructured":"Moore , C. , and Russell , A . Approximating the permanent via nonabelian determinants , 2009 . Moore, C., and Russell, A. Approximating the permanent via nonabelian determinants, 2009."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_3_2_2_17_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994","unstructured":"Papadimitriou , C. H. Computational Complexity . Addison-Wesley , 1994 . Papadimitriou, C. H. Computational Complexity. Addison-Wesley, 1994."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731540"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160230204"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993703","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:10Z","timestamp":1750244770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":20,"alternative-id":["10.1145\/1993636.1993703","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993703","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}