{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T05:07:50Z","timestamp":1734152870097,"version":"3.30.2"},"reference-count":22,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3607,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0022-0000(03)00010-2","type":"journal-article","created":{"date-parts":[[2003,6,30]],"date-time":"2003-06-30T17:29:01Z","timestamp":1056994141000},"page":"263-290","source":"Crossref","is-referenced-by-count":16,"title":["Clifford algebras and approximating the permanent"],"prefix":"10.1016","volume":"67","author":[{"given":"Steve","family":"Chien","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Rasmussen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"year":"1988","series-title":"Geometric Algebra","author":"Artin","key":"10.1016\/S0022-0000(03)00010-2_BIB1"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF03024312","article-title":"Quaternionic determinants","volume":"18","author":"Aslaksen","year":"1996","journal-title":"Math. Intelligencer"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X","article-title":"Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor","volume":"14","author":"Barvinok","year":"1999","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB4","unstructured":"A. Barvinok, New permanent estimators via non-commutative determinants, Preprint, Dept. of Mathematics, University of Michigan, Ann Arbor, July 2000."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB5","doi-asserted-by":"crossref","unstructured":"A.Z. Broder, How hard is it to marry at random? (On the approximation of the permanent), in: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1986, pp. 50\u201358. Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 551.","DOI":"10.1145\/12130.12136"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB6","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF01294460","article-title":"An analysis of a Monte Carlo algorithm for approximating the permanent","volume":"15","author":"Frieze","year":"1995","journal-title":"Combinatorica"},{"issue":"4","key":"10.1016\/S0022-0000(03)00010-2_BIB7","first-page":"1","article-title":"A theory of noncommutative determinants and characteristic functions of graphs","volume":"26","author":"Gelfand","year":"1992","journal-title":"Functional Anal. Appl."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB8","doi-asserted-by":"crossref","unstructured":"C. Godsil, I. Gutman, On the matching polynomial of a graph, Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. Janos Bolyai, 25, North-Holland, Amsterdam-New York, 1981, pp. 241\u2013249.","DOI":"10.1002\/jgt.3190050203"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB9","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","article-title":"Approximating the permanent","volume":"18","author":"Jerrum","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB10","doi-asserted-by":"crossref","unstructured":"M. Jerrum, A. Sinclair, E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2001, pp. 712\u2013721.","DOI":"10.1145\/380752.380877"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB11","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/BF01940871","article-title":"A mildly exponential approximation algorithm for the permanent","volume":"16","author":"Jerrum","year":"1996","journal-title":"Algorithmica"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB12","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1137\/0222021","article-title":"A Monte-Carlo algorithm for estimating the permanent","volume":"22","author":"Karmarkar","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB13","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/BF02183743","article-title":"Approximating the number of dimer coverings of a lattice","volume":"83","author":"Kenyon","year":"1996","journal-title":"J. Statist. Phys."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB14","unstructured":"T.-Y. Lam, The Algebraic Theory of Quadratic Forms, Benjamin\/Addison\u2013Wesley, Reading, MA, 1973 (Reprinted with revisions, 1980)."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB15","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s004930070007","article-title":"A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents","volume":"20","author":"Linial","year":"2000","journal-title":"Combinatorica"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB16","doi-asserted-by":"crossref","unstructured":"N. Nisan, Lower bounds for non-commutative computation, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1991, pp. 410\u2013418.","DOI":"10.1145\/103418.103462"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB17","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1002\/rsa.3240050208","article-title":"Approximating the permanent","volume":"5","author":"Rasmussen","year":"1994","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0022-0000(03)00010-2_BIB18","unstructured":"L.E. Rasmussen, On approximating the permanent and other #P-complete problems, Ph.D. Thesis, Computer Science Division, UC Berkeley, 1998."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB19","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"Valiant","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB20","unstructured":"B.L. van der Waerden, Algebra, Vol. 2, Frederick Ungar Publishing Co., New York, 1970."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB21","unstructured":"S. Chien, \u201cOn determinant-based algorithms for counting matchings in graphs,\u201d PhD Thesis, Computer Science Division, UC Berkeley, 2003, to appear."},{"key":"10.1016\/S0022-0000(03)00010-2_BIB22","unstructured":"H. Minc, Permanents, Encyclopedia of Mathematics and its Applications, Vol. 6, Addison\u2013Wesley Publishing Company, Reading, MA, 1982."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000102?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000102?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T03:22:46Z","timestamp":1734060166000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0022000003000102"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00010-2","relation":{},"ISSN":["0022-0000"],"issn-type":[{"type":"print","value":"0022-0000"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}