{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T20:03:14Z","timestamp":1743019394980,"version":"3.40.3"},"publisher-location":"Cham","reference-count":62,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030518240"},{"type":"electronic","value":"9783030518257"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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":[[2020]]},"DOI":"10.1007\/978-3-030-51825-7_14","type":"book-chapter","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T23:00:13Z","timestamp":1593558013000},"page":"182-200","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Simplified and Improved Separations Between Regular and General Resolution by Lifting"],"prefix":"10.1007","author":[{"given":"Marc","family":"Vinyals","sequence":"first","affiliation":[]},{"given":"Jan","family":"Elffers","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Johannsen","sequence":"additional","affiliation":[]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"issue":"1\u20133","key":"14_CR1","first-page":"51","volume":"35","author":"M Alekhnovich","year":"2005","unstructured":"Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason. 35(1\u20133), 51\u201372 (2005). Preliminary version in ICALP 2004","journal-title":"J. Autom. Reason."},{"issue":"5","key":"14_CR2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.4086\/toc.2007.v003a005","volume":"3","author":"M Alekhnovich","year":"2007","unstructured":"Alekhnovich, M., Johannsen, J., Pitassi, T., Urquhart, A.: An exponential separation between regular and general resolution. Theory Comput. 3(5), 81\u2013102 (2007). Preliminary version in STOC 2002","journal-title":"Theory Comput."},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1613\/jair.3152","volume":"40","author":"A Atserias","year":"2011","unstructured":"Atserias, A., Fichte, J.K., Thurley, M.: Clause-learning algorithms with many restarts and bounded-width resolution. J. Artif. Intell. Res. 40, 353\u2013373 (2011). Preliminary version in SAT 2009","journal-title":"J. Artif. Intell. Res."},{"key":"14_CR4","unstructured":"Audemard, G., Simon, L.: Predicting learnt clauses quality in modern SAT solvers. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 399\u2013404, July 2009"},{"key":"14_CR5","unstructured":"Bayardo Jr., R.J., Schrag, R.: Using CSP look-back techniques to solve real-world SAT instances. In: Proceedings of the 14th National Conference on Artificial Intelligence (AAAI 1997), pp. 203\u2013208, July 1997"},{"issue":"4","key":"14_CR6","doi-asserted-by":"crossref","first-page":"1612","DOI":"10.1137\/130914085","volume":"45","author":"P Beame","year":"2016","unstructured":"Beame, P., Beck, C., Impagliazzo, R.: Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. SIAM J. Comput. 45(4), 1612\u20131645 (2016). Preliminary version in STOC 2012","journal-title":"SIAM J. Comput."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Beame, P., Huynh, T., Pitassi, T.: Hardness amplification in proof complexity. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010), pp. 87\u201396, June 2010","DOI":"10.1145\/1806689.1806703"},{"issue":"3","key":"14_CR8","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1137\/060654645","volume":"37","author":"P Beame","year":"2007","unstructured":"Beame, P., Pitassi, T., Segerlind, N.: Lower bounds for Lov\u00e1sz-Schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput. 37(3), 845\u2013869 (2007). Preliminary version in ICALP 2005","journal-title":"SIAM J. Comput."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Beck, C., Nordstr\u00f6m, J., Tang, B.: Some trade-off results for polynomial calculus. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pp. 813\u2013822, May 2013","DOI":"10.1145\/2488608.2488711"},{"issue":"1","key":"14_CR10","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1002\/rsa.10089","volume":"23","author":"E Ben-Sasson","year":"2003","unstructured":"Ben-Sasson, E., Galesi, N.: Space complexity of random formulae in resolution. Random Struct. Algorithms 23(1), 92\u2013109 (2003). Preliminary version in CCC 2001","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"14_CR11","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s00493-004-0036-5","volume":"24","author":"E Ben-Sasson","year":"2004","unstructured":"Ben-Sasson, E., Impagliazzo, R., Wigderson, A.: Near optimal separation of tree-like and general resolution. Combinatorica 24(4), 585\u2013603 (2004)","journal-title":"Combinatorica"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Nordstr\u00f6m, J.: Short proofs may be spacious: an optimal separation of space and length in resolution. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 709\u2013718, October 2008","DOI":"10.1109\/FOCS.2008.42"},{"key":"14_CR13","unstructured":"Ben-Sasson, E., Nordstr\u00f6m, J.: Understanding space in proof complexity: separations and trade-offs via substitutions. In: Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS 2011), pp. 401\u2013416, January 2011"},{"issue":"2","key":"14_CR14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow-resolution made simple. J. ACM 48(2), 149\u2013169 (2001). Preliminary version in STOC 1999","journal-title":"J. ACM"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Berkholz, C., Nordstr\u00f6m, J.: Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps. In: Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2016), pp. 267\u2013276, July 2016","DOI":"10.1145\/2933575.2934560"},{"issue":"1","key":"14_CR16","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1137\/16M1109072","volume":"49","author":"C Berkholz","year":"2020","unstructured":"Berkholz, C., Nordstr\u00f6m, J.: Supercritical space-width trade-offs for resolution. SIAM J. Comput. 49(1), 98\u2013118 (2020). Preliminary version in ICALP 2016","journal-title":"SIAM J. Comput."},{"key":"14_CR17","unstructured":"Blake, A.: Canonical Expressions in Boolean Algebra. Ph.D. thesis, University of Chicago (1937)"},{"key":"14_CR18","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1613\/jair.4260","volume":"49","author":"ML Bonet","year":"2014","unstructured":"Bonet, M.L., Buss, S., Johannsen, J.: Improved separations of regular resolution from clause learning proof systems. J. Artif. Intell. Res. 49, 669\u2013703 (2014)","journal-title":"J. Artif. Intell. Res."},{"issue":"5","key":"14_CR19","doi-asserted-by":"crossref","first-page":"1462","DOI":"10.1137\/S0097539799352474","volume":"30","author":"ML Bonet","year":"2000","unstructured":"Bonet, M.L., Esteban, J.L., Galesi, N., Johannsen, J.: On the relative complexity of resolution refinements and cutting planes proof systems. SIAM J. Comput. 30(5), 1462\u20131484 (2000). Preliminary version in FOCS 1998","journal-title":"SIAM J. Comput."},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Buss, S.R., Hoffmann, J., Johannsen, J.: Resolution trees with lemmas: resolution refinements that characterize DLL-algorithms with clause learning. Logical Methods Comput. Sci. 4(4:13) (2008)","DOI":"10.2168\/LMCS-4(4:13)2008"},{"issue":"2","key":"14_CR21","first-page":"16:1","volume":"10","author":"SR Buss","year":"2014","unstructured":"Buss, S.R., Ko\u0142odziejczyk, L.: Small stone in pool. Logical Methods Comput. Sci. 10(2), 16:1\u201316:22 (2014)","journal-title":"Logical Methods Comput. Sci."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Chan, S.M.: Just a pebble game. In: Proceedings of the 28th Annual IEEE Conference on Computational Complexity (CCC 2013), pp. 133\u2013143, June 2013","DOI":"10.1109\/CCC.2013.22"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Chan, S.M., Lauria, M., Nordstr\u00f6m, J., Vinyals, M.: Hardness of approximation in PSPACE and separation results for pebble games (Extended abstract). In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), pp. 466\u2013485, October 2015","DOI":"10.1109\/FOCS.2015.36"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, A., Koucky, M., Loff, B., Mukhopadhyay, S.: Simulation beats richness: new data-structure lower bounds. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pp. 1013\u20131020, June 2018","DOI":"10.1145\/3188745.3188874"},{"issue":"3","key":"14_CR25","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"SA Cook","year":"1974","unstructured":"Cook, S.A.: An observation on time-storage trade off. J. Comput. Syst. Sci. 9(3), 308\u2013316 (1974). Preliminary version in STOC 1973","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"14_CR26","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem proving. Commun. ACM 5(7), 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"issue":"3","key":"14_CR27","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. J. ACM 7(3), 201\u2013215 (1960)","journal-title":"J. ACM"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Elffers, J., Gir\u00e1ldez-Cru, J., Gocht, S., Nordstr\u00f6m, J., Simon, L.: Seeking practical CDCL insights from theoretical SAT benchmarks. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), pp. 1300\u20131308, July 2018","DOI":"10.24963\/ijcai.2018\/181"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Garg, A., G\u00f6\u00f6s, M., Kamath, P., Sokolov, D.: Monotone circuit lower bounds from resolution. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pp. 902\u2013911, June 2018","DOI":"10.1145\/3188745.3188838"},{"key":"14_CR30","unstructured":"Gilbert, J.R., Tarjan, R.E.: Variations of a pebble game on graphs. Technical Report STAN-CS-78-661, Stanford University (1978). \n                  http:\/\/infolab.stanford.edu\/TR\/CS-TR-78-661.html"},{"issue":"4","key":"14_CR31","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1137\/0222044","volume":"22","author":"A Goerdt","year":"1993","unstructured":"Goerdt, A.: Regular resolution versus unrestricted resolution. SIAM J. Comput. 22(4), 661\u2013683 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR32","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1137\/16M109884X","volume":"47","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. SIAM J. Comput. 47(1), 241\u2013269 (2018)","journal-title":"SIAM J. Comput."},{"key":"14_CR33","unstructured":"G\u00f6\u00f6s, M., Jayram, T.S., Pitassi, T., Watson, T.: Randomized communication vs. partition number. In: Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 80, pp. 52:1\u201352:15, July 2017"},{"key":"14_CR34","unstructured":"G\u00f6\u00f6s, M., Kamath, P., Pitassi, T., Watson, T.: Query-to-communication lifting for PNP. In: Proceedings of the 32nd Annual Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 79, pp. 12:1\u201312:16, July 2017"},{"key":"14_CR35","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Lovett, S., Meka, R., Watson, T., Zuckerman, D.: Rectangles are nonnegative juntas. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pp. 257\u2013266, June 2015","DOI":"10.1145\/2746539.2746596"},{"issue":"5","key":"14_CR36","doi-asserted-by":"crossref","first-page":"1778","DOI":"10.1137\/16M1082007","volume":"47","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Pitassi, T.: Communication lower bounds via critical block sensitivity. SIAM J. Comput. 47(5), 1778\u20131806 (2018). Preliminary version in STOC 2014","journal-title":"SIAM J. Comput."},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Pitassi, T., Watson, T.: Deterministic communication vs. partition number. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), pp. 1077\u20131088, October 2015","DOI":"10.1109\/FOCS.2015.70"},{"issue":"2","key":"14_CR38","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00037-018-0166-6","volume":"27","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Pitassi, T., Watson, T.: The landscape of communication complexity classes. Comput. Complex. 27(2), 245\u2013304 (2018). Preliminary version in ICALP 2016","journal-title":"Comput. Complex."},{"issue":"4","key":"14_CR39","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc."},{"issue":"5","key":"14_CR40","doi-asserted-by":"crossref","first-page":"836","DOI":"10.1137\/0216054","volume":"16","author":"W Huang","year":"1987","unstructured":"Huang, W., Yu, X.: A DNF without regular shortest consensus path. SIAM J. Comput. 16(5), 836\u2013840 (1987)","journal-title":"SIAM J. Comput."},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Huynh, T., Nordstr\u00f6m, J.: On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity (Extended abstract). In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), pp. 233\u2013248, May 2012","DOI":"10.1145\/2213977.2214000"},{"key":"14_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-642-33558-7_25","volume-title":"Principles and Practice of Constraint Programming","author":"M J\u00e4rvisalo","year":"2012","unstructured":"J\u00e4rvisalo, M., Matsliah, A., Nordstr\u00f6m, J., \u017divn\u00fd, S.: Relating proof complexity measures and practical hardness of SAT. In: Milano, M. (ed.) CP 2012. LNCS, pp. 316\u2013331. Springer, Heidelberg (2012). \n                  https:\/\/doi.org\/10.1007\/978-3-642-33558-7_25"},{"key":"14_CR43","doi-asserted-by":"crossref","unstructured":"Kothari, P.K., Meka, R., Raghavendra, P.: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017), pp. 590\u2013603, June 2017","DOI":"10.1145\/3055399.3055438"},{"key":"14_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/978-3-319-66263-3_30","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2017","author":"M Lauria","year":"2017","unstructured":"Lauria, M., Elffers, J., Nordstr\u00f6m, J., Vinyals, M.: CNFgen: a generator of crafted benchmarks. In: Gaspers, S., Walsh, T. (eds.) SAT 2017. LNCS, vol. 10491, pp. 464\u2013473. Springer, Cham (2017). \n                  https:\/\/doi.org\/10.1007\/978-3-319-66263-3_30"},{"key":"14_CR45","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pp. 567\u2013576, June 2015","DOI":"10.1145\/2746539.2746599"},{"key":"14_CR46","unstructured":"Lingeling, Plingeling and Treengeling. \n                  http:\/\/fmv.jku.at\/lingeling\/"},{"issue":"5","key":"14_CR47","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1109\/12.769433","volume":"48","author":"JP Marques-Silva","year":"1999","unstructured":"Marques-Silva, J.P., Sakallah, K.A.: GRASP: a search algorithm for propositional satisfiability. IEEE Trans. Comput. 48(5), 506\u2013521 (1999). Preliminary version in ICCAD 1996","journal-title":"IEEE Trans. Comput."},{"key":"14_CR48","doi-asserted-by":"crossref","unstructured":"Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: engineering an efficient SAT solver. In: Proceedings of the 38th Design Automation Conference (DAC 2001), pp. 530\u2013535, June 2001","DOI":"10.1145\/378239.379017"},{"issue":"1","key":"14_CR49","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1137\/060668250","volume":"39","author":"J Nordstr\u00f6m","year":"2009","unstructured":"Nordstr\u00f6m, J.: Narrow proofs may be spacious: separating space and width in resolution. SIAM J. Comput. 39(1), 59\u2013121 (2009). Preliminary version in STOC 2006","journal-title":"SIAM J. Comput."},{"key":"14_CR50","doi-asserted-by":"crossref","first-page":"471","DOI":"10.4086\/toc.2013.v009a014","volume":"9","author":"J Nordstr\u00f6m","year":"2013","unstructured":"Nordstr\u00f6m, J., H\u00e5stad, J.: Towards an optimal separation of space and length in resolution. Theory Comput. 9, 471\u2013557 (2013). Preliminary version in STOC 2008","journal-title":"Theory Comput."},{"issue":"2","key":"14_CR51","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1016\/j.artint.2010.10.002","volume":"175","author":"K Pipatsrisawat","year":"2011","unstructured":"Pipatsrisawat, K., Darwiche, A.: On the power of clause-learning SAT solvers as resolution engines. Artif. Intell. 175(2), 512\u2013525 (2011). Preliminary version in CP 2009","journal-title":"Artif. Intell."},{"key":"14_CR52","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Robere, R.: Strongly exponential lower bounds for monotone computation. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017), pp. 1246\u20131255, June 2017","DOI":"10.1145\/3055399.3055478"},{"key":"14_CR53","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Robere, R.: Lifting Nullstellensatz to monotone span programs over any field. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pp. 1207\u20131219, June 2018","DOI":"10.1145\/3188745.3188914"},{"issue":"3","key":"14_CR54","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s004930050062","volume":"19","author":"R Raz","year":"1999","unstructured":"Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. Combinatorica 19(3), 403\u2013435 (1999). Preliminary version in FOCS 1997","journal-title":"Combinatorica"},{"issue":"2","key":"14_CR55","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/2858790","volume":"63","author":"AA Razborov","year":"2016","unstructured":"Razborov, A.A.: A new kind of tradeoffs in propositional proof complexity. J. ACM 63(2), 16:1\u201316:14 (2016)","journal-title":"J. ACM"},{"issue":"3","key":"14_CR56","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s00037-017-0163-1","volume":"27","author":"AA Razborov","year":"2018","unstructured":"Razborov, A.A.: On space and depth in resolution. Comput. Complex. 27(3), 511\u2013559 (2018)","journal-title":"Comput. Complex."},{"key":"14_CR57","doi-asserted-by":"crossref","unstructured":"de Rezende, S.F., Nordstr\u00f6m, J., Vinyals, M.: How limited interaction hinders real communication (and what it means for proof and circuit complexity). In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 295\u2013304, October 2016","DOI":"10.1109\/FOCS.2016.40"},{"key":"14_CR58","doi-asserted-by":"crossref","unstructured":"Robere, R., Pitassi, T., Rossman, B., Cook, S.A.: Exponential lower bounds for monotone span programs. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 406\u2013415, October 2016","DOI":"10.1109\/FOCS.2016.51"},{"key":"14_CR59","first-page":"115","volume-title":"Structures in Constructive Mathematics and Mathematical Logic, Part II","author":"G Tseitin","year":"1968","unstructured":"Tseitin, G.: On the complexity of derivation in propositional calculus. In: Silenko, A.O. (ed.) Structures in Constructive Mathematics and Mathematical Logic, Part II, pp. 115\u2013125. Consultants Bureau, New York-London (1968)"},{"issue":"1\u20133","key":"14_CR60","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s11225-011-9356-9","volume":"99","author":"A Urquhart","year":"2011","unstructured":"Urquhart, A.: The depth of resolution proofs. Stud. Logica. 99(1\u20133), 349\u2013364 (2011)","journal-title":"Stud. Logica."},{"issue":"1","key":"14_CR61","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1137\/090772897","volume":"40","author":"A Urquhart","year":"2011","unstructured":"Urquhart, A.: A near-optimal separation of regular and general resolution. SIAM J. Comput. 40(1), 107\u2013121 (2011). Preliminary version in SAT 2008","journal-title":"SIAM J. Comput."},{"key":"14_CR62","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/11591191_40","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"A Van Gelder","year":"2005","unstructured":"Van Gelder, A.: Pool resolution and its relation to regular resolution and DPLL with clause learning. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS (LNAI), vol. 3835, pp. 580\u2013594. Springer, Heidelberg (2005). \n                  https:\/\/doi.org\/10.1007\/11591191_40"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2020"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-51825-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,10]],"date-time":"2020-08-10T15:11:20Z","timestamp":1597072280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-51825-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030518240","9783030518257"],"references-count":62,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-51825-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"26 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Satisfiability Testing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Alghero","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 July 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sat2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/sat2020.idea-researchlab.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"69","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}