{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T20:11:42Z","timestamp":1777752702422,"version":"3.51.4"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T00:00:00Z","timestamp":1555286400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given complex numbers <jats:italic>w<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026,<jats:italic>w<jats:sub>n<\/jats:sub><\/jats:italic>, we define the weight <jats:italic>w<\/jats:italic>(<jats:italic>X<\/jats:italic>) of a set <jats:italic>X<\/jats:italic> of 0\u20131 vectors as the sum of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000105_inline1\"\/><jats:tex-math>$w_1^{x_1} \\cdots w_n^{x_n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> over all vectors (<jats:italic>x<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026,<jats:italic>x<jats:sub>n<\/jats:sub><\/jats:italic>) in <jats:italic>X<\/jats:italic>. We present an algorithm which, for a set <jats:italic>X<\/jats:italic> defined by a system of homogeneous linear equations with at most <jats:italic>r<\/jats:italic> variables per equation and at most <jats:italic>c<\/jats:italic> equations per variable, computes <jats:italic>w<\/jats:italic>(<jats:italic>X<\/jats:italic>) within relative error <jats:italic>\u220a<\/jats:italic> &gt; 0 in (<jats:italic>rc<\/jats:italic>)<jats:italic><jats:sup>O<\/jats:sup><\/jats:italic><jats:sup>(ln<\/jats:sup><jats:italic><jats:sup>n<\/jats:sup><\/jats:italic><jats:sup>-ln<\/jats:sup><jats:italic><jats:sup>\u220a<\/jats:sup><\/jats:italic><jats:sup>)<\/jats:sup> time provided <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000105_inline2\"\/><jats:tex-math>$|w_j| \\leq \\beta (r \\sqrt{c})^{-1}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for an absolute constant <jats:italic>\u03b2<\/jats:italic> &gt; 0 and all j = 1,\u2026,<jats:italic>n<\/jats:italic>. A similar algorithm is constructed for computing the weight of a linear code over <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000105_inline3\"\/><jats:tex-math>${\\mathbb F}_p$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Applications include counting weighted perfect matchings in hypergraphs, counting weighted graph homomorphisms, computing weight enumerators of linear codes with sparse code generating matrices, and computing the partition functions of the ferromagnetic Potts model at low temperatures and of the hard-core model at high fugacity on biregular bipartite graphs.<\/jats:p>","DOI":"10.1017\/s0963548319000105","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T01:58:09Z","timestamp":1555293489000},"page":"696-719","source":"Crossref","is-referenced-by-count":17,"title":["Weighted counting of solutions to sparse systems of equations"],"prefix":"10.1017","volume":"28","author":[{"given":"Alexander","family":"Barvinok","sequence":"first","affiliation":[]},{"given":"Guus","family":"Regts","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,4,15]]},"reference":[{"key":"S0963548319000105_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90135-0"},{"key":"S0963548319000105_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0511-9"},{"key":"S0963548319000105_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"S0963548319000105_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-018-2199-2"},{"key":"S0963548319000105_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58575-3"},{"key":"S0963548319000105_ref17","volume-title":"Function Theory of Several Complex Variables","author":"Krantz","year":"1992"},{"key":"S0963548319000105_ref16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.135"},{"key":"S0963548319000105_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316305"},{"key":"S0963548319000105_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.07.009"},{"key":"S0963548319000105_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.134"},{"key":"S0963548319000105_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/18.52484"},{"key":"S0963548319000105_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20414"},{"key":"S0963548319000105_ref4","unstructured":"[4] Barvinok, A. (2018) Computing permanents of complex diagonally dominant matrices and tensors. Israel J. Math., to appear. arXiv:1801.04191"},{"key":"S0963548319000105_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51829-9"},{"key":"S0963548319000105_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"S0963548319000105_ref25","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"},{"key":"S0963548319000105_ref13","volume-title":"Graph Theory","author":"Diestel","year":"2005"},{"key":"S0963548319000105_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(94)90132-5"},{"key":"S0963548319000105_ref9","unstructured":"[9] Bukh, B. (2015) Personal communication."},{"key":"S0963548319000105_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"S0963548319000105_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44479-6_7"},{"key":"S0963548319000105_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.009"},{"key":"S0963548319000105_ref14","volume-title":"Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction","author":"Friedli","year":"2018"},{"key":"S0963548319000105_ref20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548319000105_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T07:51:22Z","timestamp":1568188282000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000105\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,15]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0963548319000105"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000105","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,15]]}}}