{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:20:37Z","timestamp":1770978037821,"version":"3.50.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030311742","type":"print"},{"value":"9783030311759","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-31175-9_21","type":"book-chapter","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T10:18:17Z","timestamp":1572949097000},"page":"363-378","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximate Model Counting, Sparse XOR Constraints and Minimum Distance"],"prefix":"10.1007","author":[{"given":"Michele","family":"Boreale","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Gorla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,4]]},"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","volume-title":"Linear Algebra Methods in Combinatorics","author":"L Babai","year":"1992","unstructured":"Babai, L., Frankl, P.: Linear Algebra Methods in Combinatorics. The University of Chicago, Chicago (1992)"},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-319-73721-8_4","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"F Biondi","year":"2018","unstructured":"Biondi, F., Enescu, M.A., Heuser, A., Legay, A., Meel, K.S., Quilbeuf, J.: Scalable approximation of quantitative information flow in programs. Verification, Model Checking, and Abstract Interpretation. LNCS, vol. 10747, pp. 71\u201393. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73721-8_4"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Boreale, M., Gorla, D.: Approximate model counting, sparse XOR constraints and minimum distance. https:\/\/arxiv.org\/abs\/1907.05121 (2019)","DOI":"10.1007\/978-3-030-31175-9_21"},{"issue":"1","key":"21_CR5","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0019-9958(60)90287-4","volume":"3","author":"RC Bose","year":"1960","unstructured":"Bose, R.C., Ray-Chaudhuri, D.K.: On a class of error correcting binary group codes. Inf. Control 3(1), 68\u201379 (1960)","journal-title":"Inf. Control"},{"key":"21_CR6","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_CR7","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 International Joint Conference on Artificial Intelligence (2016)"},{"issue":"2\u20134","key":"21_CR8","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.ic.2007.07.003","volume":"206","author":"K Chatzikokolakis","year":"2008","unstructured":"Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: Anonymity protocols as noisy channels. Inf. Comput. 206(2\u20134), 378\u2013401 (2008)","journal-title":"Inf. Comput."},{"key":"21_CR9","unstructured":"Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B.: Low-density parity constraints for hashing-based discrete integration. In: Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21\u201326 June 2014, pp. 271\u2013279 (2014)"},{"key":"21_CR10","unstructured":"Fuja, T.E., Sridhara, D., Tanner, R.M.: A class of group-structured LDPC codes. In: International Symposium on Communication Theory and Applications (2001)"},{"key":"21_CR11","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4347.001.0001","volume-title":"Low Density Parity Check Codes","author":"RG Gallager","year":"1963","unstructured":"Gallager, R.G.: Low Density Parity Check Codes. MIT Press, Cambridge (1963)"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-540-72200-7_23","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"M Gebser","year":"2007","unstructured":"Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: a conflict-driven answer set solver. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 260\u2013265. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72200-7_23"},{"key":"21_CR13","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_CR14","unstructured":"Gomes, C.P., Sabharwal, A., Selman, B.: Model counting. In: Handbook of Satisfiability, pp. 633\u2013654. IOS Press (2009)"},{"key":"21_CR15","first-page":"147","volume":"2","author":"A Hocquenghem","year":"1959","unstructured":"Hocquenghem, A.: Codes correcteurs d\u2019erreurs. Chiffres 2, 147\u2013156 (1959)","journal-title":"Chiffres"},{"key":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-40196-1_16","volume-title":"Quantitative Evaluation of Systems","author":"V Klebanov","year":"2013","unstructured":"Klebanov, V., Manthey, N., Muise, C.: SAT-based analysis and quantification of information flow in programs. In: Joshi, K., Siegle, M., Stoelinga, M., D\u2019Argenio, P.R. (eds.) QEST 2013. LNCS, vol. 8054, pp. 177\u2013192. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40196-1_16"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Klebanov, V., Weigl, A., Weibarth, J.: Sound probabilistic #SAT with projection. In: Proceedings of QAPL (2016)","DOI":"10.4204\/EPTCS.227.2"},{"issue":"3","key":"21_CR18","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1109\/18.748992","volume":"45","author":"DJC MacKay","year":"1999","unstructured":"MacKay, D.J.C.: Good error-correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory 45(3), 399\u2013432 (1999)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-642-30353-1_36","volume-title":"Advances in Artificial Intelligence","author":"C Muise","year":"2012","unstructured":"Muise, C., McIlraith, S.A., Beck, J.C., Hsu, E.I.: Dsharp: fast d-DNNF compilation with sharpSAT. In: Kosseim, L., Inkpen, D. (eds.) AI 2012. LNCS (LNAI), vol. 7310, pp. 356\u2013361. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30353-1_36"},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-642-00596-1_21","volume-title":"Foundations of Software Science and Computational Structures","author":"G Smith","year":"2009","unstructured":"Smith, G.: On the foundations of quantitative information flow. In: de Alfaro, L. (ed.) FoSSaCS 2009. LNCS, vol. 5504, pp. 288\u2013302. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00596-1_21"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Soos, M., Meel, K.S.: BIRD: engineering an efficient CNF-XOR SAT solver and its applications to approximate model counting. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI) (2019)","DOI":"10.1609\/aaai.v33i01.33011592"},{"key":"21_CR22","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 . http:\/\/www.msoos.org\/cryptominisat2\/"},{"key":"21_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/11814948_38","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"M Thurley","year":"2006","unstructured":"Thurley, M.: sharpSAT \u2013 counting models with advanced component caching and implicit BCP. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 424\u2013429. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11814948_38"},{"issue":"3","key":"21_CR24","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_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(3), 85\u201393 (1986)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-31175-9_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,27]],"date-time":"2021-01-27T02:13:47Z","timestamp":1611713627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-31175-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030311742","9783030311759"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-31175-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"4 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}