{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:16:16Z","timestamp":1773796576573,"version":"3.50.1"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give a fully polynomial-time randomized approximation scheme (FPRAS) for the number of bases in bicircular matroids. This is a natural class of matroids for which counting bases exactly is #<jats:bold>P<\/jats:bold>-hard and yet approximate counting can be done efficiently.<\/jats:p>","DOI":"10.1017\/s0963548320000292","type":"journal-article","created":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T13:39:42Z","timestamp":1596721182000},"page":"124-135","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Approximately counting bases of bicircular matroids"],"prefix":"10.1017","volume":"30","author":[{"given":"Heng","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,8,6]]},"reference":[{"key":"S0963548320000292_ref28","doi-asserted-by":"crossref","unstructured":"[28] Wilson, D. B. (1996) Generating random spanning trees more quickly than the cover time. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996), pp. 296\u2013303. ACM.","DOI":"10.1145\/237814.237880"},{"key":"S0963548320000292_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/0130017"},{"key":"S0963548320000292_ref17","doi-asserted-by":"publisher","DOI":"10.1051\/proc\/201551004"},{"key":"S0963548320000292_ref13","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1015"},{"key":"S0963548320000292_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"S0963548320000292_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/18M1201846"},{"key":"S0963548320000292_ref15","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1007\/s00493-006-0039-5","article-title":"Two remarks concerning balanced matroids","volume":"26","author":"Jerrum","year":"2006","journal-title":"Combinatorica"},{"key":"S0963548320000292_ref26","doi-asserted-by":"publisher","DOI":"10.37236\/2396"},{"key":"S0963548320000292_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000639"},{"key":"S0963548320000292_ref10","article-title":"Tight bounds for popping algorithms","author":"Guo","year":"2018","journal-title":"Random Struct. Algorithms."},{"key":"S0963548320000292_ref12","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/3310131","article-title":"Uniform sampling through the Lov\u00e1sz local lemma","volume":"66","author":"Guo","year":"2019","journal-title":"J. Assoc. Comput. Mach."},{"key":"S0963548320000292_ref3","doi-asserted-by":"publisher","DOI":"10.37236\/1627"},{"key":"S0963548320000292_ref2","first-page":"371","volume-title":"Contemporary Mathematics","author":"Ch\u00e1vez Lomel\u00ed","year":"1996"},{"key":"S0963548320000292_ref21","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/28.2.213"},{"key":"S0963548320000292_ref9","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20460","article-title":"Generalized loop-erased random walks and approximate reachability","volume":"44","author":"Gorodezky","year":"2014","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000292_ref5","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1006\/eujc.1996.0031","article-title":"Strong convergence and a game of numbers","volume":"17","author":"Eriksson","year":"1996","journal-title":"European J. Combin."},{"key":"S0963548320000292_ref19","doi-asserted-by":"crossref","unstructured":"[19] Kolipaka, K. B. R. and Szegedy, M. (2011) Moser and Tardos meet Lov\u00e1sz. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011), pp. 235\u2013244. ACM.","DOI":"10.1145\/1993636.1993669"},{"key":"S0963548320000292_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007327"},{"key":"S0963548320000292_ref25","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.1997.0917","article-title":"How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph","volume":"27","author":"Propp","year":"1998","journal-title":"J. Algorithms"},{"key":"S0963548320000292_ref24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1112\/blms\/3.1.55","article-title":"The number of combinatorial geometries","volume":"3","author":"Piff","year":"1971","journal-title":"Bull. London Math. Soc."},{"key":"S0963548320000292_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316385"},{"key":"S0963548320000292_ref6","doi-asserted-by":"crossref","unstructured":"[6] Feder, T. and Mihail, M. (1992) Balanced matroids. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC \u201992), pp. 26\u201338. ACM.","DOI":"10.1145\/129712.129716"},{"key":"S0963548320000292_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S0963548320000292_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"S0963548320000292_ref7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00026-005-0239-x","article-title":"On the number of bases of bicircular matroids","volume":"9","author":"Gim\u00e9nez","year":"2005","journal-title":"Ann. Combin."},{"key":"S0963548320000292_ref4","doi-asserted-by":"crossref","unstructured":"[4] Cryan, M. , Guo, H. and Mousa, G. (2019) Modified log-Sobolev inequalities for strongly log-concave distributions. In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2019), pp. 1358\u20131370. IEEE.","DOI":"10.1109\/FOCS.2019.00083"},{"key":"S0963548320000292_ref20","unstructured":"[20] Kolmogorov, V. (2018) A faster approximation algorithm for the Gibbs partition function. In Proceedings of the 31st Conference On Learning Theory (COLT), Vol. 75 of Proceedings of Machine Learning Research, pp. 228\u2013249. PMLR."},{"key":"S0963548320000292_ref18","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1214\/15-AOP1078","article-title":"Random curves on surfaces induced from the Laplacian determinant","volume":"45","author":"Kassel","year":"2017","journal-title":"Ann. Probab."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:52:52Z","timestamp":1611229972000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000292\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,6]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0963548320000292"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000292","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,6]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}