{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T05:00:38Z","timestamp":1780981238468,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642390708","type":"print"},{"value":"9783642390715","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-39071-5_26","type":"book-chapter","created":{"date-parts":[[2013,6,23]],"date-time":"2013-06-23T21:23:17Z","timestamp":1372022597000},"page":"351-364","source":"Crossref","is-referenced-by-count":1,"title":["A Rank Lower Bound for Cutting Planes Proofs of Ramsey\u2019s Theorem"],"prefix":"10.1007","author":[{"given":"Massimo","family":"Lauria","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/0097-3165(80)90030-8","volume":"29","author":"M. Ajtai","year":"1980","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: A note on Ramsey numbers. Journal of Combinatorial Theory, Series A\u00a029(3), 354\u2013360 (1980)","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"2","key":"26_CR2","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 - resolution made simple. J. ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"26_CR3","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00222-010-0247-x","volume":"181","author":"T. Bohman","year":"2010","unstructured":"Bohman, T., Keevash, P.: The early evolution of the h-free process. Inventiones Mathematicae\u00a0181(2), 291\u2013336 (2010)","journal-title":"Inventiones Mathematicae"},{"issue":"4","key":"26_CR4","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s000370100000","volume":"10","author":"M.L. Bonet","year":"2001","unstructured":"Bonet, M.L., Galesi, N.: Optimality of size-width tradeoffs for resolution. Computational Complexity\u00a010(4), 261\u2013276 (2001)","journal-title":"Computational Complexity"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Bonet, M.L., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 575\u2013584. ACM (1995)","DOI":"10.1145\/225058.225275"},{"issue":"3","key":"26_CR6","doi-asserted-by":"publisher","first-page":"708","DOI":"10.2307\/2275569","volume":"62","author":"M.L. Bonet","year":"1997","unstructured":"Bonet, M.L., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic\u00a062(3), 708\u2013728 (1997)","journal-title":"The Journal of Symbolic Logic"},{"issue":"4","key":"26_CR7","doi-asserted-by":"publisher","first-page":"65","DOI":"10.4086\/toc.2006.v002a004","volume":"2","author":"J. Buresh-Oppenheim","year":"2006","unstructured":"Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting planes procedures. Theory of Computing\u00a02(4), 65\u201390 (2006)","journal-title":"Theory of Computing"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Carlucci, L., Galesi, N., Lauria, M.: Paris-harrington tautologies. In: Proc. of IEEE 26th Conference on Computational Complexity, pp. 93\u2013103 (2011)","DOI":"10.1109\/CCC.2011.17"},{"issue":"4","key":"26_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics\u00a04(4), 305\u2013337 (1973)","journal-title":"Discrete Mathematics"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114","author":"V. Chv\u00e1tal","year":"1989","unstructured":"Chv\u00e1tal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra and its Applications\u00a0114, 455\u2013499 (1989)","journal-title":"Linear Algebra and its Applications"},{"issue":"2","key":"26_CR11","doi-asserted-by":"publisher","first-page":"941","DOI":"10.4007\/annals.2009.170.941","volume":"170","author":"D. Conlon","year":"2009","unstructured":"Conlon, D.: A new upper bound for diagonal ramsey numbers. Annals of Mathematics\u00a0170(2), 941\u2013960 (2009)","journal-title":"Annals of Mathematics"},{"issue":"1","key":"26_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook, W., Coullard, C.R., Tur\u00e1n, G.: On the complexity of cutting-plane proofs. Discrete Applied Mathematics\u00a018(1), 25\u201338 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u00f6s","year":"1947","unstructured":"Erd\u00f6s, P.: Some remarks on the theory of graphs. Bull. Amer. Math. Soc\u00a053, 292\u2013294 (1947)","journal-title":"Bull. Amer. Math. Soc"},{"key":"26_CR14","first-page":"49","volume-title":"Classic Papers in Combinatorics, Modern Birkh\u00e4user Classics","author":"P. Erd\u0151s","year":"1987","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. In: Gessel, I., Rota, G.-C. (eds.) Classic Papers in Combinatorics, Modern Birkh\u00e4user Classics, pp. 49\u201356. Birkh\u00e4user, Boston (1987)"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1838552.1838556","volume":"12","author":"N. Galesi","year":"2010","unstructured":"Galesi, N., Lauria, M.: Optimality of size-degree tradeoffs for polynomial calculus. ACM Transaction on Computational Logic 12, 4:1\u20134:22 (2010)","journal-title":"ACM Transaction on Computational Logic"},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BFb0023762","volume-title":"Computer Science Logic","author":"A. Goerdt","year":"1992","unstructured":"Goerdt, A.: The cutting plane proof system with bounded degree of falsity. In: B\u00f6rger, E., J\u00e4ger, G., Kleine B\u00fcning, H., Richter, M.M. (eds.) CSL 1991. LNCS, vol.\u00a0626, pp. 119\u2013133. Springer, Heidelberg (1992)"},{"issue":"5","key":"26_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R.E. Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society\u00a064(5), 275\u2013278 (1958)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/11499107_10","volume-title":"Theory and Applications of Satisfiability Testing","author":"E.A. Hirsch","year":"2005","unstructured":"Hirsch, E.A., Nikolenko, S.I.: Simulating cutting plane proofs with restricted degree of falsity by resolution. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 135\u2013142. Springer, Heidelberg (2005)"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Pitassi, T., Urquhart, A.: Upper and lower bounds for tree-like cutting planes proofs. In: Proceedings of the Symposium on Logic in Computer Science, LICS 1994, pp. 220\u2013228. IEEE (1994)","DOI":"10.1109\/LICS.1994.316069"},{"issue":"2","key":"26_CR20","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. Computational Complexity\u00a08(2), 127\u2013144 (1999)","journal-title":"Computational Complexity"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Jukna, S.: Boolean Function Complexity: Advances and Frontiers. Springer (2012)","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"3","key":"26_CR22","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/rsa.3240070302","volume":"7","author":"J.H. Kim","year":"1995","unstructured":"Kim, J.H.: The Ramsey number r(3,t) has order of magnitude t\n2\/log(t). Random Structures and Algorithms\u00a07(3), 173\u2013208 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00153-010-0212-9","volume":"50","author":"J. Kraj\u00ed\u010dek","year":"2011","unstructured":"Kraj\u00ed\u010dek, J.: A note on propositional proof complexity of some Ramsey-type statements. Archive for Mathematical Logic\u00a050, 245\u2013255 (2011), doi:10.1007\/s00153-010-0212-9","journal-title":"Archive for Mathematical Logic"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, B., Moll, R.N.: Examples of hard tautologies in the propositional calculus. In: 13th ACM Symposium on Th. of Computing, STOC 1981, pp. 28\u201337 (1981)","DOI":"10.1145\/800076.802454"},{"key":"26_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/3-540-54487-9_67","volume-title":"Computer Science Logic","author":"P. Pudl\u00e1k","year":"1991","unstructured":"Pudl\u00e1k, P.: Ramsey\u2019s theorem in Bounded Arithmetic. In: Sch\u00f6nfeld, W., B\u00f6rger, E., Kleine B\u00fcning, H., Richter, M.M. (eds.) CSL 1990. LNCS, vol.\u00a0533, pp. 308\u2013317. Springer, Heidelberg (1991)"},{"issue":"3","key":"26_CR26","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower bounds for Resolution and Cutting Plane proofs and monotone computations. Journal of Symbolic Logic\u00a062(3), 981\u2013998 (1997)","journal-title":"Journal of Symbolic Logic"},{"issue":"14-15","key":"26_CR27","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1016\/j.ipl.2012.05.004","volume":"112","author":"P. Pudl\u00e1k","year":"2012","unstructured":"Pudl\u00e1k, P.: A lower bound on the size of resolution proofs of the ramsey theorem. Inf. Process. Lett.\u00a0112(14-15), 610\u2013611 (2012)","journal-title":"Inf. Process. Lett."},{"key":"26_CR28","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0012-365X(77)90044-9","volume":"20","author":"J. Spencer","year":"1977","unstructured":"Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discrete Mathematics\u00a020, 69\u201376 (1977)","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2013"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39071-5_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T04:46:31Z","timestamp":1780980391000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-39071-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390708","9783642390715"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39071-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}