{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:48:14Z","timestamp":1751582894563,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175169"},{"type":"electronic","value":"9783642175176"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_9","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:13:41Z","timestamp":1291407221000},"page":"73-84","source":"Crossref","is-referenced-by-count":10,"title":["Improved Randomized Algorithms for 3-SAT"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[]},{"given":"Kazuhisa","family":"Seto","sequence":"additional","affiliation":[]},{"given":"Tadashi","family":"Takai","sequence":"additional","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The probabilistic method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The probabilistic method, 3rd edn. Wiley Interscience, Hoboken (2008)","edition":"3"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-24605-3_12","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Baumer","year":"2004","unstructured":"Baumer, S., Schuler, R.: Improving a probabilistic 3-SAT algorithm by dynamic search and independent clause pairs. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 150\u2013161. Springer, Heidelberg (2004)"},{"issue":"1-3","key":"9_CR3","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T. Br\u00fceggemann","year":"2004","unstructured":"Br\u00fceggemann, T., Kern, W.: An improved deterministic local search algorithm for 3-SAT. Theoretical Computer Science\u00a0329(1-3), 303\u2013313 (2004)","journal-title":"Theoretical Computer Science"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1007\/BF01084392","volume":"22","author":"E. Dantsin","year":"1983","unstructured":"Dantsin, E.: Two systems for proving tautologies based on the split method. Journal of Mathematical Science\u00a022, 1293\u20131305 (1983)","journal-title":"Journal of Mathematical Science"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic $2 - \\frac{2}{k+1}$ algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-45841-7_15","volume-title":"STACS 2002","author":"T. Hofmeister","year":"2002","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A probabilistic 3-SAT algorithm further improved. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 192\u2013202. Springer, Heidelberg (2002)"},{"key":"9_CR7","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 328\u2013329 (2004)"},{"issue":"1-2","key":"9_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science\u00a0223(1-2), 1\u201372 (1999)","journal-title":"Theoretical Computer Science"},{"key":"9_CR9","first-page":"331","volume":"1984","author":"H. Luckhardt","year":"1984","unstructured":"Luckhardt, H.: Obere Komplexit\u00e4tsschranken f\u00fcr TAUT-Entscheidungen. In: Proceedings of Frege Conference 1984, pp. 331\u2013337 (1984)","journal-title":"Proceedings of Frege Conference"},{"key":"9_CR10","unstructured":"Monien, B., Speckenmeyer, E.: 3-Satisfiability is testable in O(1.62 r ) steps. Technical Report Beicht Nr. 3\/1979, Reihe Theoretische Informatik, Universit\u00e4t-Gesamthochschule-Paderborn (1979)"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Solving satisfiability less than 2 n steps. Discrete Applied Mathematics\u00a010, 287\u2013295 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"issue":"3","key":"9_CR13","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R. Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. Journal of the ACM\u00a052(3), 337\u2013364 (2005)","journal-title":"Journal of the ACM"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. In: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 566\u2013574 (1997)","DOI":"10.1109\/SFCS.1997.646146"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/3-540-61732-9_59","volume-title":"Artificial Intelligence and Symbolic Mathematical Computation","author":"R. Rodosek","year":"1996","unstructured":"Rodosek, R.: A new approach on solving 3-Satisfiability. In: Pfalzgraf, J., Calmet, J., Campbell, J. (eds.) AISMC 1996. LNCS, vol.\u00a01138, pp. 197\u2013212. Springer, Heidelberg (1996)"},{"key":"9_CR16","volume-title":"3-SAT \u2208 RTIME(O(1.32971 n )). Diploma thesis, Department Of Computer Science","author":"D. Rolf","year":"2003","unstructured":"Rolf, D.: 3-SAT \u2208 RTIME(O(1.32971 n )). Diploma thesis, Department Of Computer Science, Humboldt University Berlin, Germany (Janury 2003)"},{"key":"9_CR17","unstructured":"Rolf, D.: 3-SAT \u2208 RTIME(O(1.32793n)). Electronic Colloquium on Computational Complexity, TR03-054 (2003)"},{"key":"9_CR18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.3233\/SAT190005","volume":"1","author":"D. Rolf","year":"2006","unstructured":"Rolf, D.: Improved bound for the PPSZ\/Sch\u00f6ning-algorithm for 3-SAT. Journal on Satisfiability, Boolean Modeling and Computation\u00a01, 111\u2013122 (2006)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-540-78773-0_6","volume-title":"LATIN 2008: Theoretical Informatics","author":"D. Scheder","year":"2008","unstructured":"Scheder, D.: Guided search and a faster deterministic algorithm for 3-SAT. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 60\u201371. Springer, Heidelberg (2008)"},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/3-540-56992-8_22","volume-title":"Computer Science Logic","author":"I. Schiermeyer","year":"1993","unstructured":"Schiermeyer, I.: Solving 3-Satisfiability in less than 1.579 n steps. In: Martini, S., B\u00f6rger, E., Kleine B\u00fcning, H., J\u00e4ger, G., Richter, M.M. (eds.) CSL 1992. LNCS, vol.\u00a0702, pp. 379\u2013394. Springer, Heidelberg (1993)"},{"key":"9_CR21","unstructured":"Schiermeyer, I.: Pure literal look ahead: An O(1.497 n ) 3-Satisfiability algorithm. In: Proceedings of the Workshop on the Satisfiability Problem, pp. 127\u2013136 (1996)"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A Probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T12:13:38Z","timestamp":1740744818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}