{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T03:10:29Z","timestamp":1741230629635,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642215803"},{"type":"electronic","value":"9783642215810"}],"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-21581-0_4","type":"book-chapter","created":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T13:30:19Z","timestamp":1307712619000},"page":"19-32","source":"Crossref","is-referenced-by-count":1,"title":["Satisfiability Certificates Verifiable in Subexponential Time"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Dantsin","sequence":"first","affiliation":[]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","first-page":"252","volume-title":"Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC 2006","author":"C. Calabro","year":"2006","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC 2006, pp. 252\u2013260. IEEE Computer Society, Los Alamitos (2006)"},{"issue":"1","key":"4_CR2","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.H., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2 \u2212 2\/(k + 1))n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"4_CR3","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, ch. 12, pp. 403\u2013424. IOS Press, Amsterdam (2009)"},{"key":"4_CR4","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006)"},{"issue":"2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. Journal of Computer and System Sciences\u00a062(2), 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR7","series-title":"The Art of Computer Programming, fascicle\u00a03","first-page":"1","volume-title":"Generating All Combinations and Partitions","author":"D.E. Knuth","year":"2005","unstructured":"Knuth, D.E.: Generating All Combinations and Partitions. The Art of Computer Programming, fascicle\u00a03, vol.\u00a04, pp. 1\u20136. Addison-Wesley, Reading (2005)"},{"key":"4_CR8","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011","author":"R.A. Moser","year":"2011","unstructured":"Moser, R.A., Scheder, D.: A full derandomization of Sch\u00f6ning\u2019s k-SAT algorithm. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011. ACM, New York (2011) (to appear)"},{"key":"4_CR9","first-page":"241","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC 2010","author":"R. Paturi","year":"2010","unstructured":"Paturi, R., Pudl\u00e1k, P.: On the complexity of circuit satisfiability. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC 2010, pp. 241\u2013250. ACM, New York (2010)"},{"key":"4_CR10","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 1998, pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"4_CR11","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 1997, pp. 566\u2013574 (1997)","DOI":"10.1109\/SFCS.1997.646146"},{"key":"4_CR12","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 1999, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jalgor.2004.04.012","volume":"54","author":"R. Schuler","year":"2005","unstructured":"Schuler, R.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms\u00a054(1), 40\u201344 (2005)","journal-title":"Journal of Algorithms"},{"key":"4_CR14","first-page":"231","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC 2010","author":"R. Williams","year":"2010","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC 2010, pp. 231\u2013240. ACM, New York (2010)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21581-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T02:49:33Z","timestamp":1741229373000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21581-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642215803","9783642215810"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21581-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}