{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:47Z","timestamp":1759639067551,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_65","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"774-785","source":"Crossref","is-referenced-by-count":8,"title":["On the Limits of Sparsification"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Santhanam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"65_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"65_CR2","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: Proceedings of IEEE Conference on Computational Complexity, pp. 252\u2013260 (2006)","DOI":"10.1109\/CCC.2006.6"},{"key":"65_CR3","unstructured":"Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC0. In: Proceedings of Symposium on Discrete Algorithms (to appear, 2012)"},{"issue":"4","key":"65_CR4","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.: On the complexity of k-sat. Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"65_CR5","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences\u00a062(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"8","key":"65_CR6","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1536616.1536637","volume":"52","author":"S. Malik","year":"2009","unstructured":"Malik, S., Zhang, L.: Boolean satisfiability from theoretical hardness to practical success. Communications of the ACM\u00a052(8), 76\u201382 (2009)","journal-title":"Communications of the ACM"},{"issue":"1-2","key":"65_CR7","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.tcs.2005.07.029","volume":"347","author":"P.B. Miltersen","year":"2005","unstructured":"Miltersen, P.B., Radhakrishnan, J., Wegener, I.: On converting cnf to dnf. Theoretical Computer Science\u00a0347(1-2), 325\u2013335 (2005)","journal-title":"Theoretical Computer Science"},{"key":"65_CR8","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudlak, P., Saks, M., Zane, F.: An improved exponential-time algorithm for k-sat. In: Proceedings of 39th International Symposium on Foundations of Computer Sciece (FOCS), pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"65_CR9","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudlak, P., Zane, F.: Satisfiability coding lemma. In: Proceedings of 38th International Symposium on Foundations of Computer Science (FOCS), pp. 566\u2013574 (1997)","DOI":"10.1109\/SFCS.1997.646146"},{"key":"65_CR10","doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In: Proceedings of 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 183\u2013192 (2010)","DOI":"10.1109\/FOCS.2010.25"},{"key":"65_CR11","first-page":"131","volume":"18","author":"R. Santhanam","year":"2011","unstructured":"Santhanam, R., Srinivasan, S.: On the limits of sparsification. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 131 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"1","key":"65_CR12","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":"65_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-08353-7_135","volume-title":"Mathematical Foundations of Computer Science 1977","author":"L.G. Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph-Theoretic Arguments in Low-Level Complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol.\u00a053, pp. 162\u2013176. Springer, Heidelberg (1977)"},{"key":"65_CR14","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 231\u2013240 (2010)","DOI":"10.1145\/1806689.1806723"},{"key":"65_CR15","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. In: Proceedings of 26th Annual IEEE Conference on Computational Complexity, pp. 115\u2013125 (2011)","DOI":"10.1109\/CCC.2011.36"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:12:02Z","timestamp":1743595922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}