{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T16:00:13Z","timestamp":1758124813858},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319942049"},{"type":"electronic","value":"9783319942056"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94205-6_21","type":"book-chapter","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T12:22:50Z","timestamp":1530274970000},"page":"312-328","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A New Probabilistic Algorithm for Approximate Model Counting"],"prefix":"10.1007","author":[{"given":"Cunjing","family":"Ge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifei","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xutong","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,30]]},"reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-66263-3_1","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2017","author":"D Achlioptas","year":"2017","unstructured":"Achlioptas, D., Theodoropoulos, P.: Probabilistic model counting with short XORs. In: Gaspers, S., Walsh, T. (eds.) SAT 2017. LNCS, vol. 10491, pp. 3\u201319. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66263-3_1"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Bayardo, Jr, R.J., Schrag, R.: Using CSP look-back techniques to solve real-world SAT instances. In: Proceedings of AAAI, pp. 203\u2013208 (1997)","DOI":"10.1007\/3-540-61551-2_65"},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1006\/inco.2000.2885","volume":"163","author":"M Bellare","year":"2000","unstructured":"Bellare, M., Goldreich, O., Petrank, E.: Uniform generation of NP-witnesses using an NP-oracle. Inf. Comput. 163(2), 510\u2013526 (2000)","journal-title":"Inf. Comput."},{"key":"21_CR4","unstructured":"Belle, V., Broeck, G.V., Passerini, A.: Hashing-based approximate probabilistic inference in hybrid domains. In: Proceedings of UAI, pp. 141\u2013150 (2015)"},{"issue":"2","key":"21_CR5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1214\/ss\/1009213286","volume":"16","author":"LD Brown","year":"2001","unstructured":"Brown, L.D., Cai, T.T., Dasgupta, A.: Interval estimation for a binomial proportion. Stat. Sci. 16(2), 101\u2013133 (2001)","journal-title":"Stat. Sci."},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-642-00768-2_16","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"R Brummayer","year":"2009","unstructured":"Brummayer, R., Biere, A.: Boolector: an efficient SMT solver for bit-vectors and arrays. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505, pp. 174\u2013177. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00768-2_16"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Fremont, D.J., Meel, K.S., Seshia, S.A., Vardi, M.Y.: Distribution-aware sampling and weighted model counting for SAT. In: Proceedings of AAAI, pp. 1722\u20131730 (2014)","DOI":"10.1609\/aaai.v28i1.8990"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Meel, K.S., Mistry, R., Vardi, M.Y.: Approximate probabilistic inference via word-level counting. In: Proceedings of AAAI, pp. 3218\u20133224 (2016)","DOI":"10.1609\/aaai.v30i1.10416"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-642-39799-8_40","volume-title":"Computer Aided Verification","author":"S Chakraborty","year":"2013","unstructured":"Chakraborty, S., Meel, K.S., Vardi, M.Y.: A scalable and nearly uniform generator of SAT witnesses. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 608\u2013623. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39799-8_40"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-642-40627-0_18","volume-title":"Principles and Practice of Constraint Programming","author":"S Chakraborty","year":"2013","unstructured":"Chakraborty, S., Meel, K.S., Vardi, M.Y.: A scalable approximate model counter. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 200\u2013216. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40627-0_18"},{"key":"21_CR11","unstructured":"Chakraborty, S., Meel, K.S., Vardi, M.Y.: Algorithmic improvements in approximate counting for probabilistic inference: from linear to logarithmic SAT calls. In: Proceedings of IJCAI, pp. 3569\u20133576 (2016)"},{"issue":"6\u20137","key":"21_CR12","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1016\/j.artint.2007.11.002","volume":"172","author":"M Chavira","year":"2008","unstructured":"Chavira, M., Darwiche, A.: On probabilistic inference by weighted model counting. Artif. Intell. 172(6\u20137), 772\u2013799 (2008)","journal-title":"Artif. Intell."},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-662-46681-0_26","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"D Chistikov","year":"2015","unstructured":"Chistikov, D., Dimitrova, R., Majumdar, R.: Approximate counting in SMT and value estimation for probabilistic programs. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 320\u2013334. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46681-0_26"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1613\/jair.2289","volume":"30","author":"C Domshlak","year":"2007","unstructured":"Domshlak, C., Hoffmann, J.: Probabilistic planning via heuristic forward search and weighted model counting. J. Artif. Intell. Res. (JAIR) 30, 565\u2013620 (2007)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"21_CR15","first-page":"2085","volume":"26","author":"S Ermon","year":"2013","unstructured":"Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B.: Embed and project: discrete sampling with universal hashing. Adv. Neural Inf. Process. Syst. 26, 2085\u20132093 (2013)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"21_CR16","unstructured":"Ermon, S., Gomes, C.P., Selman, B.: Uniform solution sampling using a constraint solver as an oracle. In: Proceedings of UAI, pp. 255\u2013264 (2012)"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Filieri, A., Pasareanu, C.S., Visser, W.: Reliability analysis in symbolic pathfinder: a brief summary. In: Proceedings of ICSE, pp. 39\u201340 (2014)","DOI":"10.1109\/ICSE.2013.6606608"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Filieri, A., Pasareanu, C.S., Yang, G.: Quantification of software changes through probabilistic symbolic execution (N). In: Proceedings of ASE, pp. 703\u2013708 (2015)","DOI":"10.1109\/ASE.2015.78"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Fredrikson, M., Jha, S.: Satisfiability modulo counting: a new approach for analyzing privacy properties. In: Proceedings of CSL-LICS, pp. 42:1\u201342:10 (2014)","DOI":"10.1145\/2603088.2603097"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Geldenhuys, J., Dwyer, M.B., Visser, W.: Probabilistic symbolic execution. In: Proceedings of ISSTA, pp. 166\u2013176 (2012)","DOI":"10.1145\/2338965.2336773"},{"key":"21_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-319-21690-4_11","volume-title":"Computer Aided Verification","author":"K Gleissenthall von","year":"2015","unstructured":"von Gleissenthall, K., K\u00f6pf, B., Rybalchenko, A.: Symbolic polytopes for quantitative interpolation and verification. In: Kroening, D., P\u0103s\u0103reanu, C.S. (eds.) CAV 2015. LNCS, vol. 9206, pp. 178\u2013194. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21690-4_11"},{"key":"21_CR22","unstructured":"Gomes, C.P., Hoffmann, J., Sabharwal, A., Selman, B.: From sampling to model counting. In: Proceedings of IJCAI, pp. 2293\u20132299 (2007)"},{"key":"21_CR23","unstructured":"Gomes, C.P., Sabharwal, A., Selman, B.: Model counting: a new strategy for obtaining good bounds. In: Proceedings of AAAI, pp. 54\u201361 (2006)"},{"key":"21_CR24","first-page":"481","volume":"19","author":"CP Gomes","year":"2006","unstructured":"Gomes, C.P., Sabharwal, A., Selman, B.: Near-uniform sampling of combinatorial spaces using XOR constraints. Adv. Neural Inf. Process. Syst. 19, 481\u2013488 (2006)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"1","key":"21_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s10601-015-9204-z","volume":"21","author":"A Ivrii","year":"2016","unstructured":"Ivrii, A., Malik, S., Meel, K.S., Vardi, M.Y.: On computing minimal independent support and its applications to sampling and counting. Constraints 21(1), 41\u201358 (2016)","journal-title":"Constraints"},{"issue":"3","key":"21_CR26","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"RM Karp","year":"1989","unstructured":"Karp, R.M., Luby, M., Madras, N.: Monte-carlo approximation algorithms for enumeration problems. J. Algorithms 10(3), 429\u2013448 (1989)","journal-title":"J. Algorithms"},{"issue":"1","key":"21_CR27","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10479-009-0680-7","volume":"184","author":"L Kroc","year":"2011","unstructured":"Kroc, L., Sabharwal, A., Selman, B.: Leveraging belief propagation, backtrack search, and statistics for model counting. Ann. OR 184(1), 209\u2013231 (2011)","journal-title":"Ann. OR"},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Liu, S., Zhang, J.: Program analysis: from qualitative analysis to quantitative analysis. In: Proceedings of ICSE, pp. 956\u2013959 (2011)","DOI":"10.1145\/1985793.1985957"},{"key":"21_CR29","unstructured":"Meel, K.S., Vardi, M.Y., Chakraborty, S., Fremont, D.J., Seshia, S.A., Fried, D., Ivrii, A., Malik, S.: Constrained sampling and counting: universal hashing meets SAT solving. In: Proceedings of Workshop on Beyond NP (BNP) (2016)"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"Phan, Q., Malacaria, P., Pasareanu, C.S., d\u2019Amorim, M.: Quantifying information leaks using reliability analysis. In: Proceedings of SPIN, pp. 105\u2013108 (2014)","DOI":"10.1145\/2632362.2632367"},{"issue":"1\u20132","key":"21_CR31","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D Roth","year":"1996","unstructured":"Roth, D.: On the hardness of approximate reasoning. Artif. Intell. 82(1\u20132), 273\u2013302 (1996)","journal-title":"Artif. Intell."},{"key":"21_CR32","unstructured":"Sang, T., Bacchus, F., Beame, P., Kautz, H.A., Pitassi, T.: Combining component caching and clause learning for effective model counting. In: Proceedings of SAT (2004)"},{"key":"21_CR33","unstructured":"Sang, T., Beame, P., Kautz, H.A.: Performing bayesian inference by weighted model counting. In: Proceedings of AAAI, pp. 475\u2013482 (2005)"},{"key":"21_CR34","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 330\u2013335 (1983)","DOI":"10.1145\/800061.808762"},{"key":"21_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-02777-2_24","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"M Soos","year":"2009","unstructured":"Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 244\u2013257. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02777-2_24"},{"key":"21_CR36","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J.: The complexity of approximate counting (preliminary version). In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 118\u2013126 (1983)","DOI":"10.1145\/800061.808740"},{"issue":"3","key":"21_CR37","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"21_CR38","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1080\/09296174.2013.799918","volume":"20","author":"S Wallis","year":"2013","unstructured":"Wallis, S.: Binomial confidence intervals and contingency tests: mathematical fundamentals and the evaluation of alternative methods. J. Quant. Linguist. 20(3), 178\u2013208 (2013)","journal-title":"J. Quant. Linguist."},{"key":"21_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/11499107_24","volume-title":"Theory and Applications of Satisfiability Testing","author":"W Wei","year":"2005","unstructured":"Wei, W., Selman, B.: A new approach to model counting. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 324\u2013339. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11499107_24"},{"issue":"158","key":"21_CR40","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1080\/01621459.1927.10502953","volume":"22","author":"EB Wilson","year":"1927","unstructured":"Wilson, E.B.: Probable inference, the law of succession and statistical inference. J. Am. Stat. Assoc. 22(158), 209\u2013212 (1927)","journal-title":"J. Am. Stat. Assoc."}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94205-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T15:34:47Z","timestamp":1661528087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-94205-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319942049","9783319942056"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94205-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}