{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T11:41:09Z","timestamp":1705059669295},"reference-count":19,"publisher":"Elsevier BV","issue":"9","content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1016\/j.ipl.2013.02.013","type":"journal-article","created":{"date-parts":[[2013,2,26]],"date-time":"2013-02-26T20:00:58Z","timestamp":1361908858000},"page":"337-344","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":3,"title":["Exploiting independent subformulas: A faster approximation scheme for #k-SAT"],"prefix":"10.1016","volume":"113","author":[{"given":"Manuel","family":"Schmitt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Wanka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.ipl.2013.02.013_br0010","first-page":"199","article-title":"Threshold phenomena: The computer scientist\u02bcs viewpoint","volume":"80","author":"Stamatiou","year":"2003","journal-title":"Bulletin of the EATCS"},{"key":"10.1016\/j.ipl.2013.02.013_br0020","series-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/j.ipl.2013.02.013_br0030","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","article-title":"A linear-time algorithm for testing the truth of certain quantified boolean formulas","volume":"8","author":"Aspvall","year":"1979","journal-title":"Information Processing Letters"},{"key":"10.1016\/j.ipl.2013.02.013_br0040","doi-asserted-by":"crossref","unstructured":"K. Makinoa, S. Tamaki, M. Yamamoto, Derandomizing HSSW algorithm for 3-SAT, in: Proc. 17th Int. Computing and Combinatorics Conference (COCOON), 2011, pp. 1\u201312.","DOI":"10.1007\/978-3-642-22685-4_1"},{"key":"10.1016\/j.ipl.2013.02.013_br0050","doi-asserted-by":"crossref","unstructured":"T. Hertli, 3-SAT faster and simpler \u2013 Unique-SAT bounds for PPSZ hold in general, in: Proc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), 2011, pp. 277\u2013284.","DOI":"10.1109\/FOCS.2011.22"},{"key":"10.1016\/j.ipl.2013.02.013_br0060","series-title":"Approximation Algorithms for NP-Hard Problems","first-page":"482","article-title":"The Markov chain Monte-Carlo method: An approach to approximate counting and integration","author":"Jerrum","year":"1996"},{"key":"10.1016\/j.ipl.2013.02.013_br0070","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"8","author":"Valiant","year":"1979","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/j.ipl.2013.02.013_br0080","doi-asserted-by":"crossref","unstructured":"M. Wahlstr\u00f6m, A tighter bound for counting max-weight solutions to 2SAT instances, in: Proc. 3rd Int. Workshop on Parameterized and Exact Computation (IWPEC), 2008, pp. 202\u2013213.","DOI":"10.1007\/978-3-540-79723-4_19"},{"key":"10.1016\/j.ipl.2013.02.013_br0090","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ipl.2007.06.017","article-title":"New upper bound for the #3-SAT problem","volume":"105","author":"Kutzkov","year":"2007","journal-title":"Information Processing Letters"},{"key":"10.1016\/j.ipl.2013.02.013_br0100","unstructured":"M. Thurley, An approximation algorithm for #k-SAT, in: Proc. 29th Int. Symp. on Theoretical Aspects of Computer Science (STACS), 2012, pp. 78\u201387."},{"key":"10.1016\/j.ipl.2013.02.013_br0110","doi-asserted-by":"crossref","unstructured":"R.A. Moser, D. Scheder, A full derandomization of Sch\u00f6ning\u02bcs k-SAT algorithm, in: Proc. 43rd ACM Symp. on Theory of Computing (STOC), 2011, pp. 245\u2013252.","DOI":"10.1145\/1993636.1993670"},{"key":"10.1016\/j.ipl.2013.02.013_br0120","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(91)90315-S","article-title":"Counting the number of solutions for instances of satisfiability","volume":"81","author":"Dubois","year":"1991","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.ipl.2013.02.013_br0130","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(95)00144-1","article-title":"Number of models and satisfiability of sets of clauses","volume":"155","author":"Zhang","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.ipl.2013.02.013_br0140","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","article-title":"An improved exponential-time algorithm for k-SAT","volume":"52","author":"Paturi","year":"2005","journal-title":"Journal of the ACM"},{"key":"10.1016\/j.ipl.2013.02.013_br0150","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, W. Matthews, R. Paturi, A satisfiability algorithm for AC0, in: Proc. 23rd ACM\u2013SIAM Symp. on Discrete Algorithms (SODA), 2012, pp. 961\u2013972.","DOI":"10.1137\/1.9781611973099.77"},{"key":"10.1016\/j.ipl.2013.02.013_br0160","series-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"10.1016\/j.ipl.2013.02.013_br0170","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","article-title":"Monte-Carlo approximation algorithms for enumeration problems","volume":"10","author":"Karp","year":"1989","journal-title":"Journal of Algorithms"},{"key":"10.1016\/j.ipl.2013.02.013_br0180","doi-asserted-by":"crossref","unstructured":"T. Hofmeister, U. Sch\u00f6ning, R. Schuler, O. Watanabe, A probabilistic 3-SAT algorithm further improved, in: Proc. 19th Int. Symp. on Theoretical Aspects of Computer Science (STACS), 2002, pp. 193\u2013202.","DOI":"10.1007\/3-540-45841-7_15"},{"key":"10.1016\/j.ipl.2013.02.013_br0190","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00224-005-1275-6","article-title":"Randomized algorithms for 3-SAT","volume":"40","author":"Hofmeister","year":"2007","journal-title":"Theory of Computing Systems"}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019013000677?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019013000677?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,7,10]],"date-time":"2019-07-10T00:21:52Z","timestamp":1562718112000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019013000677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5]]},"references-count":19,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["S0020019013000677"],"URL":"https:\/\/doi.org\/10.1016\/j.ipl.2013.02.013","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[2013,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Exploiting independent subformulas: A faster approximation scheme for #k-SAT","name":"articletitle","label":"Article Title"},{"value":"Information Processing Letters","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ipl.2013.02.013","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2013 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}