{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T07:47:52Z","timestamp":1720770472442},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T00:00:00Z","timestamp":1454284800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00493-015-3193-9","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T10:15:50Z","timestamp":1454321750000},"page":"253-268","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["The complexity of proving that a graph is Ramsey"],"prefix":"10.1007","volume":"37","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","published-online":{"date-parts":[[2016,2,1]]},"reference":[{"key":"3193_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/S0097539701389944","volume":"34","author":"M. Alekhnovich","year":"2004","unstructured":"M. Alekhnovich, E. Ben-Sasson, A. A. Razborov and A. Wigderson: Pseudorandom generators in propositional proof complexity, SIAM Journal on Computing, 34 (2004), 67\u201388, a preliminary version appeared in FOCS \u201900.","journal-title":"SIAM Journal on Computing"},{"key":"3193_CR2","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.jcss.2007.06.025","volume":"74","author":"A. Atserias","year":"2008","unstructured":"A. Atserias and V. Dalmau: A combinatorial characterization of resolution width, J. Comput. Syst. Sci., 74 (2008), 323\u2013334.","journal-title":"J. Comput. Syst. Sci."},{"key":"3193_CR3","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1613\/jair.3152","volume":"40","author":"A. Atserias","year":"2011","unstructured":"A. Atserias, J. K. Fichte and M. Thurley: Clause-learning algorithms with many restarts and bounded-width resolution, J. Artif. Intell. Res. (JAIR), 40 (2011), 353\u2013373.","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"3193_CR4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/301250.301392","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","author":"E. Ben-Sasson","year":"1999","unstructured":"E. Ben-Sasson and A. Wigderson: Short proofs are narrow - resolution made simple, in: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 517\u2013526, 1999."},{"key":"3193_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2499937.2499941","volume":"14","author":"O. Beyersdorff","year":"2013","unstructured":"O. Beyersdorff, N. Galesi and M. Lauria: Parameterized complexity of DPLL search procedures, ACM Transactions on Computational Logic, 14 (2013), 1\u201321.","journal-title":"ACM Transactions on Computational Logic"},{"key":"3193_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2355580.2355582","volume":"4","author":"O. Beyersdorff","year":"2012","unstructured":"O. Beyersdorff, N. Galesi, M. Lauria and A. A. Razborov: Parameterized bounded-depth Frege is not optimal, ACM Trans. Comput. Theory, 4 (2012), 1\u201316.","journal-title":"ACM Trans. Comput. Theory"},{"key":"3193_CR7","first-page":"93","volume-title":"Proc. of IEEE 26th Conference on Computational Complexity","author":"L. Carlucci","year":"2011","unstructured":"L. Carlucci, N. Galesi and M. Lauria: Paris-Harrington tautologies, in: Proc. of IEEE 26th Conference on Computational Complexity, 93\u2013103, 2011."},{"key":"3193_CR8","volume-title":"AK Peters, Ltd.","author":"F. R. K. Chung","year":"1998","unstructured":"F. R. K. Chung, P. Erd\u0151s and R. L. Graham: Erd\u0151s on Graphs: His Legacy of Unsolved Problems, AK Peters, Ltd., 1 edition, 1998."},{"key":"3193_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00037-010-0001-1","volume":"20","author":"S. Dantchev","year":"2011","unstructured":"S. Dantchev, B. Martin and S. Szeider: Parameterized proof complexity, Computational Complexity, 20 (2011), 51\u201385.","journal-title":"Computational Complexity"},{"key":"3193_CR10","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u0151s","year":"1947","unstructured":"P. Erd\u0151s: Some remarks on the theory of graphs, Bull. Amer. Math. Soc, 53 (1947), 292\u2013294.","journal-title":"Bull. Amer. Math. Soc"},{"key":"3193_CR11","first-page":"197","volume-title":"Bulletin of Symbolic Logic","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"J. Kraj\u00ed\u010dek: Tautologies from pseudo-random generators, Bulletin of Symbolic Logic, 197\u2013212, 2001."},{"key":"3193_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"J. Kraj\u00ed\u010dek: Lower bounds to the size of constant-depth propositional proofs, Journal of Symbolic Logic, 59 (1994), 73\u201386.","journal-title":"Journal of Symbolic Logic"},{"key":"3193_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00153-010-0212-9","volume":"50","author":"J. Kraj\u00ed\u010dek","year":"2011","unstructured":"J. Kraj\u00ed\u010dek: A note on propositional proof complexity of some Ramsey-type statements, Archive for Mathematical Logic, 50 (2011), 245\u2013255.","journal-title":"Archive for Mathematical Logic"},{"key":"3193_CR14","first-page":"28","volume-title":"STOC 1981, 13th ACM Symposium on Th. of Computing","author":"B. Krishnamurthy","year":"1981","unstructured":"B. Krishnamurthy and R. N. Moll: Examples of hard tautologies in the propositional calculus, in: STOC 1981, 13th ACM Symposium on Th. of Computing, 28\u201337, 1981."},{"key":"3193_CR15","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1016\/j.artint.2010.10.002","volume":"175","author":"K. Pipatsrisawat","year":"2011","unstructured":"K. Pipatsrisawat and A. Darwiche: On the power of clause-learning SAT solvers as resolution engines, Articial Intelligence, 175 (2011), 512\u2013525.","journal-title":"Articial Intelligence"},{"key":"3193_CR16","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1006\/jcta.1999.2972","volume":"88","author":"H. Pr\u00f6mel","year":"1999","unstructured":"H. Pr\u00f6mel and V. R\u00f6dl: Non-Ramsey graphs are c log n-universal, Journal of Combinatorial Theory, Series A, 88 (1999), 379\u2013384.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"3193_CR17","first-page":"308","volume-title":"Proceedings of Computer Science Logic 1990","author":"P. Pudl\u00e1k","year":"1991","unstructured":"P. Pudl\u00e1k: Ramsey\u2019s theorem in Bounded Arithmetic, in: Proceedings of Computer Science Logic 1990, 308\u2013317, 1991."},{"key":"3193_CR18","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1016\/j.ipl.2012.05.004","volume":"112","author":"P. Pudl\u00e1k","year":"2012","unstructured":"P. Pudl\u00e1k: A lower bound on the size of resolution proofs of the Ramsey theorem, Inf. Process. Lett., 112 (2012), 610\u2013611.","journal-title":"Inf. Process. Lett."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3193-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-015-3193-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3193-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3193-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T21:58:50Z","timestamp":1654207130000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-015-3193-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["3193"],"URL":"https:\/\/doi.org\/10.1007\/s00493-015-3193-9","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,1]]}}}