{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:55:07Z","timestamp":1725738907532},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_58","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"684-695","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Proving That a Graph Is Ramsey"],"prefix":"10.1007","author":[{"given":"Massimo","family":"Lauria","sequence":"first","affiliation":[]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[]},{"given":"Neil","family":"Thapen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"58_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":"3","key":"58_CR2","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":"58_CR3","doi-asserted-by":"crossref","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. (JAIR)\u00a040, 353\u2013373 (2011)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow - resolution made simple. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 517\u2013526 (1999)","DOI":"10.1145\/301250.301392"},{"issue":"3","key":"58_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2355580.2355582","volume":"4","author":"O. Beyersdorff","year":"2012","unstructured":"Beyersdorff, O., Galesi, N., Lauria, M., Razborov, A.A.: Parameterized bounded-depth frege is not optimal. ACM Trans. Comput. Theory\u00a04(3), 7:1\u20137:16 (2012)","journal-title":"ACM Trans. Comput. Theory"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Blake, A.: Canonical Expressions in Boolean Algebra. PhD thesis, University of Chicago (1938)","DOI":"10.2307\/2267595"},{"issue":"2","key":"58_CR7","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"},{"key":"58_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"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Chung, F.R.K., Erd\u0151s, P., Graham, R.L.: Erd\u0151s on Graphs: His Legacy of Unsolved Problems, 1st edn. AK Peters, Ltd. (January 1998)","DOI":"10.1201\/9781439863879"},{"issue":"2","key":"58_CR10","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"},{"key":"58_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00037-010-0001-1","volume":"20","author":"S. Dantchev","year":"2011","unstructured":"Dantchev, S., Martin, B., Szeider, S.: Parameterized proof complexity. Computational Complexity\u00a020, 51\u201385 (2011), doi:10.1007\/s00037-010-0001-1","journal-title":"Computational Complexity"},{"key":"58_CR12","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":"58_CR13","series-title":"Modern Birkh\u00e4user Classics","first-page":"49","volume-title":"Classic Papers in Combinatorics","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)"},{"issue":"3","key":"58_CR14","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\n                  2\/log(t). Random Structures and Algorithms\u00a07(3), 173\u2013208 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"58_CR15","doi-asserted-by":"crossref","unstructured":"Krajicek, J.: Tautologies from pseudo-random generators. Bulletin of Symbolic Logic, 197\u2013212 (2001)","DOI":"10.2307\/2687774"},{"issue":"1","key":"58_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"Kraj\u00ed\u010dek, J.: Lower bounds to the size of constant-depth propositional proofs. Journal of Symbolic Logic\u00a059(1), 73\u201386 (1994)","journal-title":"Journal of Symbolic Logic"},{"key":"58_CR17","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":"58_CR18","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, B., Moll, R.N.: Examples of hard tautologies in the propositional calculus. In: STOC 1981, 13th ACM Symposium on Th. of Computing, pp. 28\u201337 (1981)","DOI":"10.1145\/800076.802454"},{"issue":"2","key":"58_CR19","doi-asserted-by":"publisher","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. Artificial Intelligence\u00a0175(2), 512\u2013525 (2011)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"58_CR20","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1006\/jcta.1999.2972","volume":"88","author":"H. Pr\u00f6mel","year":"1999","unstructured":"Pr\u00f6mel, H., R\u00f6dl, V.: Non-ramsey graphs are c log n-universal. Journal of Combinatorial Theory, Series A\u00a088(2), 379\u2013384 (1999)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"58_CR21","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":"14-15","key":"58_CR22","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":"58_CR23","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","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:07:22Z","timestamp":1557896842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}