{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T18:16:57Z","timestamp":1781288217651,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642392054","type":"print"},{"value":"9783642392061","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_37","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"437-448","source":"Crossref","is-referenced-by-count":10,"title":["Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Filmus","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mladen","family":"Mik\u0161a","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Vinyals","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"37_CR1","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/S0097539700366735","volume":"31","author":"M. Alekhnovich","year":"2002","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Space complexity in propositional calculus. SIAM J. Comput.\u00a031(4), 1184\u20131211 (2002)","journal-title":"SIAM J. Comput."},{"key":"37_CR2","first-page":"18","volume":"242","author":"M. Alekhnovich","year":"2003","unstructured":"Alekhnovich, M., Razborov, A.A.: Lower bounds for polynomial calculus: Non-binomial case. Proc. Inst. Math.\u00a0242, 18\u201335 (2003)","journal-title":"Proc. Inst. Math."},{"issue":"3","key":"37_CR3","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.jcss.2007.06.025","volume":"74","author":"A. Atserias","year":"2008","unstructured":"Atserias, A., Dalmau, V.: A combinatorial characterization of resolution width. J. Comput. Syst. Sci.\u00a074(3), 323\u2013334 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR4","unstructured":"Bayardo Jr., R.J., Schrag, R.: Using CSP look-back techniques to solve real-world SAT instances. In: Proc. 14th National Conference on Artificial Intelligence (AAAI\u00a01997), pp. 203\u2013208 (1997)"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Beame, P., Beck, C., Impagliazzo, R.: Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear space. In: Proc. 44th Symposium on Theory of Computing (STOC\u00a02012), pp. 213\u2013232 (2012)","DOI":"10.1145\/2213977.2213999"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Beck, C., Nordstrm\u0308, J., Tang, B.: Some trade-off results for polynomial calculus. In: Proc. 45th Symposium on Theory of Computing, STOC\u00a02013 (2013)","DOI":"10.1145\/2488608.2488711"},{"issue":"6","key":"37_CR7","doi-asserted-by":"publisher","first-page":"2511","DOI":"10.1137\/080723880","volume":"38","author":"E. Ben-Sasson","year":"2009","unstructured":"Ben-Sasson, E.: Size space tradeoffs for resolution. SIAM J. Comput.\u00a038(6), 2511\u20132525 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"37_CR8","doi-asserted-by":"publisher","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\u00a023(1), 92\u2013109 (2003)","journal-title":"Random Struct. Algorithms"},{"key":"37_CR9","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: Proc. 49th Symposium on Foundations of Computer Science (FOCS\u00a02008), pp. 709\u2013718 (2008)","DOI":"10.1109\/FOCS.2008.42"},{"key":"37_CR10","unstructured":"Ben-Sasson, E., Nordstr\u00f6m, J.: Understanding space in proof complexity: Separations and trade-offs via substitutions. In: Proc. 2nd Symposium on Innovations in Computer Science (ICS\u00a02011), pp. 401\u2013416 (2011)"},{"issue":"2","key":"37_CR11","doi-asserted-by":"publisher","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\u2014resolution made simple. J. ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"J. ACM"},{"key":"37_CR12","unstructured":"Blake, A.: Canonical Expressions in Boolean Algebra. PhD thesis, University of Chicago (1937)"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"Bonacina, I., Galesi, N.: Pseudo-partitions, transversality and locality: A combinatorial characterization for the space measure in algebraic proof systems. In: Proc. 4th Conference on Innovations in Theoretical Computer Science (ITCS\u00a02013), pp. 455\u2013472 (2013)","DOI":"10.1145\/2422436.2422486"},{"issue":"4","key":"37_CR14","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"Chv\u00e1tal, V., Szemer\u00e9di, E.: Many hard examples for resolution. J. ACM\u00a035(4), 759\u2013768 (1988)","journal-title":"J. ACM"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proc. 28th Symposium on Theory of Computing (STOC\u00a01996), pp. 174\u2013183 (1996)","DOI":"10.1145\/237814.237860"},{"issue":"1","key":"37_CR16","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.: The relative efficiency of propositional proof systems. J. Symb. Log.\u00a044(1), 36\u201350 (1979)","journal-title":"J. Symb. Log."},{"issue":"1","key":"37_CR17","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1006\/inco.2001.2921","volume":"171","author":"J.L. Esteban","year":"2001","unstructured":"Esteban, J.L., Tor\u00e1n, J.: Space bounds for resolution. Inf. Comput.\u00a0171(1), 84\u201397 (2001)","journal-title":"Inf. Comput."},{"key":"37_CR18","doi-asserted-by":"crossref","unstructured":"Filmus, Y., Lauria, M., Nordstr\u00f6m, J., Thapen, N., Ron-Zewi, N.: Space complexity in polynomial calculus. In: Proc. 27th Conference on Computational Complexity (CCC\u00a02012), pp. 334\u2013344 (2012)","DOI":"10.1109\/CCC.2012.27"},{"issue":"2-3","key":"37_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"Haken, A.: The intractability of resolution. Theor. Comput. Sci.\u00a039(2-3), 297\u2013308 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR20","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. In: Proc. 44th Symposium on Theory of Computing (STOC\u00a02012), pp. 233\u2013248 (2012)","DOI":"10.1145\/2213977.2214000"},{"issue":"2","key":"37_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s000370050024","volume":"8","author":"R. Impagliazzo","year":"1999","unstructured":"Impagliazzo, R., Pudl\u00e1k, P., Sgall, J.: Lower bounds for the polynomial calculus and the Gr\u00f6bner basis algorithm. Comput. Complex.\u00a08(2), 127\u2013144 (1999)","journal-title":"Comput. Complex."},{"key":"37_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jctb.2000.1991","volume":"81","author":"J.H. Kim","year":"2001","unstructured":"Kim, J.H., Wormald, N.C.: Random matchings which induce Hamilton cycles, and hamiltonian decompositions of random regular graphs. J. Comb. Theory B\u00a081, 20\u201344 (2001)","journal-title":"J. Comb. Theory B"},{"key":"37_CR23","unstructured":"Marques-Silva, J.P., Sakallah, K.A.: GRASP\u2014a new search algorithm for satisfiability. In: Proc. International Conference on Computer-Aided Design (ICCAD 1996), pp. 220\u2013227 (1996)"},{"issue":"4","key":"37_CR24","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s000370050013","volume":"7","author":"A.A. Razborov","year":"1998","unstructured":"Razborov, A.A.: Lower bounds for the polynomial calculus. Comput. Complex.\u00a07(4), 291\u2013324 (1998)","journal-title":"Comput. Complex."},{"issue":"1","key":"37_CR25","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"Urquhart, A.: Hard examples for resolution. J. ACM\u00a034(1), 209\u2013219 (1987)","journal-title":"J. ACM"}],"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-39206-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:07:17Z","timestamp":1557911237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}