{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T13:40:16Z","timestamp":1741441216770,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642226847"},{"type":"electronic","value":"9783642226854"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22685-4_1","type":"book-chapter","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T08:54:39Z","timestamp":1312966479000},"page":"1-12","source":"Crossref","is-referenced-by-count":9,"title":["Derandomizing HSSW Algorithm for 3-SAT"],"prefix":"10.1007","author":[{"given":"Kazuhisa","family":"Makino","sequence":"first","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]},{"given":"Masaki","family":"Yamamoto","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Annals of Mathematics\u00a0160(2), 781\u2013793 (2004)","journal-title":"Annals of Mathematics"},{"key":"1_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":"1_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":"1_CR4","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic Algorithms for the Lov\u00e1sz Local Lemma. In: Proc. of SODA 2010, pp. 992\u20131004 (2010)","DOI":"10.1137\/1.9781611973075.80"},{"issue":"1","key":"1_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., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2\u2009\u2212\u20092\/(k\u2009+\u20091)) n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"1_CR6","series-title":"Frontiers in Artificial Intelligence and Applications","first-page":"403","volume-title":"Handbook of Satisfiability","author":"E. Dantsin","year":"2009","unstructured":"Dantsin, E., Hirsch, E.A.: Worst-Case Upper Bounds. In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol.\u00a0185, pp. 403\u2013424. IOS Press, Amsterdam (2009)"},{"key":"1_CR7","unstructured":"Hertli, T., Moser, R.A., Scheder, D.: Improving PPSZ for 3-SAT using Crititical Variables. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 237\u2013248 (2011)"},{"key":"1_CR8","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":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-17517-6_9","volume-title":"Algorithms and Computation","author":"K. Iwama","year":"2010","unstructured":"Iwama, K., Seto, K., Takai, T., Tamaki, S.: Improved Randomized Algorithms for 3-SAT. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol.\u00a06506, pp. 73\u201384. Springer, Heidelberg (2010)"},{"key":"1_CR10","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 328\u2013329 (2004)"},{"key":"1_CR11","unstructured":"Kutzkov, K., Scheder, D.: Using CSP To Improve Deterministic 3-SAT. arXiv:1007.1166v2 (2010)"},{"key":"1_CR12","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 in less than 2 n steps. Discrete Applied Mathematics\u00a010, 287\u2013295 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Moser, R., Scheder, D.: A Full Derandomization of Sch\u00f6ning\u2019s k-SAT Algorithm. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 245\u2013252 (2011) arXiv:1008.4067v1","DOI":"10.1145\/1993636.1993670"},{"issue":"5","key":"1_CR14","doi-asserted-by":"publisher","first-page":"1641","DOI":"10.1137\/S0097539796309326","volume":"28","author":"S. Mahajan","year":"1999","unstructured":"Mahajan, S., Ramesh, H.: Derandomizing Approximation Algorithms Based on Semidefinite Programming. SIAM J. Comput.\u00a028(5), 1641\u20131663 (1999)","journal-title":"SIAM J. Comput."},{"key":"#cr-split#-1_CR15.1","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M., Zane, F.: An Improve 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"},{"key":"#cr-split#-1_CR15.2","unstructured":"Journal version: J.\u00a0of the ACM 52(3), 337\u2013364 (2005)"},{"key":"1_CR16","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":"1_CR17","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM\u00a055(4), Article 17 (2008)","DOI":"10.1145\/1391289.1391291"},{"key":"1_CR18","unstructured":"Rolf, D.: 3-SAT \u2208 RTIME(O(1.32793n)). Electronic Colloquium on Computational Complexity, TR03-054 (2003)"},{"key":"1_CR19","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":"1_CR20","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"},{"key":"1_CR21","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)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22685-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T13:22:14Z","timestamp":1741440134000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22685-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642226847","9783642226854"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22685-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}