{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T04:23:24Z","timestamp":1768623804903,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642112683","type":"print"},{"value":"9783642112690","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_6","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"75-85","source":"Crossref","is-referenced-by-count":70,"title":["The Complexity of Satisfiability of Small Depth Circuits"],"prefix":"10.1007","author":[{"given":"Chris","family":"Calabro","sequence":"first","affiliation":[]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[]},{"given":"Ramamohan","family":"Paturi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching (May 1996)"},{"key":"6_CR2","unstructured":"Calabro, C.: A lower bound on the size of series-parallel graphs dense in long paths. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a015(110) (2008)"},{"issue":"3","key":"6_CR3","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","volume":"74","author":"C. Calabro","year":"2008","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of unique k-sat: An isolation lemma for k-cnfs. J. Comput. Syst. Sci.\u00a074(3), 386\u2013393 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR4","first-page":"252","volume-title":"CCC 2006: Proceedings of the 21st Annual IEEE Conference on Computational Complexity","author":"C. Calabro","year":"2006","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for sat. In: CCC 2006: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, Washington, DC, USA, 2006, pp. 252\u2013260. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/11499107_31","volume-title":"Theory and Applications of Satisfiability Testing","author":"E. Dantsin","year":"2005","unstructured":"Dantsin, E., Wolpert, A.: An improved upper bound for sat. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 400\u2013407. Springer, Heidelberg (2005)"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"2","key":"6_CR7","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. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"6_CR8","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? J. Comput. Syst. Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR9","unstructured":"Nurik, S.: Personal communication. To appear in ECCC (2009)"},{"issue":"3","key":"6_CR10","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. J. ACM\u00a052(3), 337\u2013364 (2005)","journal-title":"J. ACM"},{"key":"6_CR11","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science\u00a0115 ( December 1999)"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00001598","volume":"9","author":"R. Paturi","year":"2000","unstructured":"Paturi, R., Saks, M.E., Zane, F.: Exponential lower bounds for depth 3 boolean circuits. Computational Complexity\u00a09(1), 1\u201315 (2000); Preliminary version in 29th annual ACM Symposium on Theory of Computing, pp. 96\u201391 (1997)","journal-title":"Computational Complexity"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: FOCS, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"1","key":"6_CR14","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. J. Algorithms\u00a054(1), 40\u201344 (2005)","journal-title":"J. Algorithms"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","volume-title":"Mathematical Foundations of Computer Science 1977","author":"L. Valiant","year":"1977","unstructured":"Valiant, L.: Graph-theoretic arguments in low level complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol.\u00a053, Springer, Heidelberg (1977)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T14:46:32Z","timestamp":1739457992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}