{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:35Z","timestamp":1740109295935,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,12,23]],"date-time":"2019-12-23T00:00:00Z","timestamp":1577059200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,23]],"date-time":"2019-12-23T00:00:00Z","timestamp":1577059200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00654-w","type":"journal-article","created":{"date-parts":[[2019,12,23]],"date-time":"2019-12-23T08:03:00Z","timestamp":1577088180000},"page":"1474-1489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving and Sampling with Many Solutions"],"prefix":"10.1007","volume":"82","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4746-7364","authenticated-orcid":false,"given":"Jerri","family":"Nummenpalo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emo","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,23]]},"reference":[{"issue":"3","key":"654_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"key":"654_CR2","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time $$o(1.3446^n)$$: a no-MIS algorithm. In: 36th IEEE Annual Symposium on Foundations of Computer Science, (FOCS), vol.\u00a036, pp. 444\u2013452 (1995)"},{"key":"654_CR3","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1007\/978-3-642-15369-3_38","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Anindya De","year":"2010","unstructured":"De, A., Etesami, O., Trevisan, L., Tulsiani, M.: Improved pseudorandom generators for depth 2 circuits. In: 13th International Workshop, APPROX, and 14th International Workshop Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, RANDOM, pp. 504\u2013517 (2010)"},{"issue":"2","key":"654_CR4","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/120868177","volume":"43","author":"T Hertli","year":"2014","unstructured":"Hertli, T.: 3-SAT faster and simpler\u2013unique-SAT bounds for PPSZ hold in general. SIAM J. Comput. 43(2), 718\u2013729 (2014)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"654_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1093\/jigpal\/6.1.59","volume":"6","author":"EA Hirsch","year":"1998","unstructured":"Hirsch, E.A.: A fast deterministic algorithm for formulas that have many satisfying assignments. Logic J IGPL 6(1), 59\u201371 (1998)","journal-title":"Logic J IGPL"},{"key":"654_CR6","doi-asserted-by":"crossref","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A probabilistic 3\u2013SAT algorithm further improved. In: Annual Symposium on Theoretical Aspects of Computer Science, pp. 192\u2013202. Springer (2002)","DOI":"10.1007\/3-540-45841-7_15"},{"issue":"3","key":"654_CR7","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00224-005-1275-6","volume":"40","author":"T Hofmeister","year":"2007","unstructured":"Hofmeister, T., Schoning, U., Schuler, R., Watanabe, O.: Randomized algorithms for 3-SAT. Theory Comput. Syst. 40(3), 249\u2013262 (2007)","journal-title":"Theory Comput. Syst."},{"key":"654_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating: Algorithms and Complexity","author":"MR Jerrum","year":"2003","unstructured":"Jerrum, M.R.: Counting, Sampling and Integrating: Algorithms and Complexity. Springer, Berlin (2003)"},{"key":"654_CR9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"MR Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"654_CR10","first-page":"176","volume":"20","author":"DM Kane","year":"2013","unstructured":"Kane, D.M., Watanabe, O.: A short implicant of CNFs with relatively many satisfying assignments. Electron. Colloq. Comput. Complex. 20, 176 (2013)","journal-title":"Electron. Colloq. Comput. Complex."},{"issue":"1","key":"654_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2007.06.017","volume":"105","author":"K Kutzkov","year":"2007","unstructured":"Kutzkov, K.: New upper bound for the #3-SAT problem. Inf. Process. Lett. 105(1), 1\u20135 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"654_CR12","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"654_CR13","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: AAAI Workshop: Beyond NP (2016)"},{"issue":"3","key":"654_CR14","first-page":"13","volume":"28","author":"Y Naveh","year":"2007","unstructured":"Naveh, Y., Rimon, M., Jaeger, I., Katz, Y., Vinov, M., Marcus, E., Shurek, G.: Constraint-based random stimuli generation for hardware verification. AI Mag. 28(3), 13 (2007)","journal-title":"AI Mag."},{"key":"654_CR15","unstructured":"Sang, T., Beame, P., Kautz, H.A.: Performing Bayesian inference by weighted model counting. In AAAI, vol.\u00a05, pp. 475\u2013481 (2005)"},{"issue":"9","key":"654_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.ipl.2013.02.013","volume":"113","author":"M Schmitt","year":"2013","unstructured":"Schmitt, M., Wanka, R.: Exploiting independent subformulas: a faster approximation scheme for #k-SAT. Inf. Process. Lett. 113(9), 337\u2013344 (2013)","journal-title":"Inf. Process. Lett."},{"key":"654_CR17","doi-asserted-by":"crossref","unstructured":"Servedio, R.A., Tan, L.Y.: Deterministic search for CNF satisfying assignments in almost polynomial time. In: 58th IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pp. 813\u2013823 (2017)","DOI":"10.1109\/FOCS.2017.80"},{"key":"654_CR18","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: A note on approximate counting for k-DNF. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 417\u2013425. Springer (2004)","DOI":"10.1007\/978-3-540-27821-4_37"},{"key":"654_CR19","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: International Workshop on Parameterized and Exact Computation, pp. 202\u2013213. Springer (2008)","DOI":"10.1007\/978-3-540-79723-4_19"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00654-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00654-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00654-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T00:21:29Z","timestamp":1608596489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00654-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,23]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["654"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00654-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,12,23]]},"assertion":[{"value":"16 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}