{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T05:46:51Z","timestamp":1782366411683,"version":"3.54.5"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319243177","type":"print"},{"value":"9783319243184","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24318-4_4","type":"book-chapter","created":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T01:42:56Z","timestamp":1441935776000},"page":"33-45","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP"],"prefix":"10.1007","author":[{"given":"Ruiwen","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,10,27]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 75\u201385. Springer, Heidelberg (2009)"},{"issue":"1\u20133","key":"4_CR2","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.dam.2003.03.002","volume":"142","author":"J Chen","year":"2004","unstructured":"Chen, J., Kanj, I.: Improved exact algorithms for max-sat. Discrete Applied Mathematics 142(1\u20133), 17\u201327 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. In: Proceedings of the 29th Annual IEEE Conference on Computational Complexity, CCC 2014 (2014)","DOI":"10.1109\/CCC.2014.34"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-662-44465-8_15","volume-title":"Mathematical Foundations of Computer Science 2014","author":"R Chen","year":"2014","unstructured":"Chen, R., Kabanets, V., Saurabh, N.: An improved deterministic #SAT algorithm for small de morgan formulas. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 165\u2013176. Springer, Heidelberg (2014)"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/11814948_26","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"E Dantsin","year":"2006","unstructured":"Dantsin, E., Wolpert, A.: MAX-SAT for formulas with constant clause density can be solved faster than in $${{\\cal O}}(2^{n})$$ time. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 266\u2013276. Springer, Heidelberg (2006)"},{"issue":"5","key":"4_CR6","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F Fomin","year":"2009","unstructured":"Fomin, F., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1\u201325:32 (2009)","journal-title":"J. ACM"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.jcss.2011.05.010","volume":"78","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Sorkin, G.: A universally fastest algorithm for max 2-sat, max 2-csp, and everything in between. J. Comput. Syst. Sci. 78(1), 305\u2013335 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2014.01.010","volume":"526","author":"A Golovnev","year":"2014","unstructured":"Golovnev, A., Kutzkov, K.: New exact algorithms for the 2-constraint satisfaction problem. Theor. Comput. Sci. 526, 18\u201327 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/rsa.3240040202","volume":"4","author":"R Impagliazzo","year":"1993","unstructured":"Impagliazzo, R., Nisan, N.: The effect of random restrictions on formula size. Random Structures and Algorithms 4(2), 121\u2013134 (1993)","journal-title":"Random Structures and Algorithms"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth two threshold circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October 26\u201329, 2013, pp. 479\u2013488 (2013)","DOI":"10.1109\/FOCS.2013.58"},{"issue":"1","key":"4_CR11","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ipl.2005.11.013","volume":"98","author":"M Koivisto","year":"2006","unstructured":"Koivisto, M.: Optimal 2-constraint satisfaction via sum-product algorithms. Inf. Process. Lett. 98(1), 24\u201328 (2006)","journal-title":"Inf. Process. Lett."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Raz, R., Tal, A.: Improved average-case lower bounds for demorgan formula size. In: Proceedings of the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science, pp. 588\u2013597 (2013)","DOI":"10.1109\/FOCS.2013.69"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-74510-5_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"AS Kulikov","year":"2007","unstructured":"Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol. 4649, pp. 194\u2013204. Springer, Heidelberg (2007)"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/rsa.3240040203","volume":"4","author":"M Paterson","year":"1993","unstructured":"Paterson, M., Zwick, U.: Shrinkage of de Morgan formulae under restriction. Random Structures and Algorithms 4(2), 135\u2013150 (1993)","journal-title":"Random Structures and Algorithms"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-319-09284-3_4","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"T Sakai","year":"2014","unstructured":"Sakai, T., Seto, K., Tamaki, S.: Solving sparse instances of Max SAT via width reduction and greedy restriction. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 32\u201347. Springer, Heidelberg (2014)"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Fighting perebor: new and improved algorithms for formula and qbf satisfiability. In: Proceedings of the Fifty-First Annual IEEE Symposium on Foundations of Computer Science, pp. 183\u2013192 (2010)","DOI":"10.1109\/FOCS.2010.25"},{"issue":"1","key":"4_CR17","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 54(1), 40\u201344 (2005)","journal-title":"J. Algorithms"},{"issue":"3\u20134","key":"4_CR18","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.disopt.2007.08.001","volume":"4","author":"A Scott","year":"2007","unstructured":"Scott, A., Sorkin, G.: Linear-programming design and analysis of fast algorithms for max 2-csp. Discret. Optim. 4(3\u20134), 260\u2013287 (2007)","journal-title":"Discret. Optim."},{"issue":"2\u20133","key":"4_CR19","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing -- SAT 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24318-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T05:07:00Z","timestamp":1782364020000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-24318-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319243177","9783319243184"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24318-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 October 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}