{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:55:36Z","timestamp":1742972136521,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_4","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"44-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Short Proofs of the Kneser-Lov\u00e1sz Coloring Principle"],"prefix":"10.1007","author":[{"given":"James","family":"Aisenberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria Luisa","family":"Bonet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Buss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Cr\u00e3ciun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Istrate","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"4_CR1","unstructured":"Aisenberg, J., Bonet, M.L., Buss, S.R.: Quasi-polynomial size Frege proofs of Frankl\u2019s theorem on the trace of finite sets (201?) (to appear in Journal of Symbolic Logic)"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-1-4612-2566-9_3","volume-title":"Feasible Mathematics II","author":"ML Bonet","year":"1995","unstructured":"Bonet, M.L., Buss, S.R., Pitassi, T.: Are there hard examples for Frege systems? In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 30\u201356. Birkh\u00e4user, Boston (1995)"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"916","DOI":"10.2307\/2273826","volume":"52","author":"SR Buss","year":"1987","unstructured":"Buss, S.R.: Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic 52, 916\u2013927 (1987)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-642-58622-4_5","volume-title":"Computational Logic","author":"SR Buss","year":"1999","unstructured":"Buss, S.R.: Propositional proof complexity: An introduction. In: Berger, U., Schwichtenberg, H. (eds.) Computational Logic, pp. 127\u2013178. Springer, Berlin (1999)"},{"issue":"9","key":"4_CR5","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1016\/j.apal.2012.01.015","volume":"163","author":"SR Buss","year":"2012","unstructured":"Buss, S.R.: Towards NP-P via proof complexity and proof search. Annals of Pure and Applied Logic 163(9), 1163\u20131182 (2012)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Buss, S.R.: Quasipolynomial size proofs of the propositional pigeonhole principle (2014) (submitted for publication)","DOI":"10.1016\/j.tcs.2015.02.005"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"SA Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44, 36\u201350 (1979)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/978-3-319-09284-3_11","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"G Istrate","year":"2014","unstructured":"Istrate, G., Cr\u00e3ciun, A.: Proof complexity and the Kneser-Lov\u00e1sz theorem. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 138\u2013153. Springer, Heidelberg (2014)"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.apal.2003.12.003","volume":"124","author":"E Je\u0159\u00e1bek","year":"2004","unstructured":"Je\u0159\u00e1bek, E.: Dual weak pigeonhole principle, boolean complexity, and derandomization. Annals of Pure and Applied Logic 124, 1\u201337 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J.: Bounded Arithmetic. Propositional Calculus and Complexity Theory. Cambridge University Press, Heidelberg (1995)","DOI":"10.1017\/CBO9780511529948"},{"issue":"3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A 25(3), 319\u2013324 (1978)","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00493-004-0011-1","volume":"24","author":"J Matou\u0161ek","year":"2004","unstructured":"Matou\u0161ek, J.: A combinatorial proof of Kneser\u2019s conjecture. Combinatorica 24(1), 163\u2013170 (2004)","journal-title":"Combinatorica"},{"issue":"4","key":"4_CR13","doi-asserted-by":"publisher","first-page":"417","DOI":"10.2178\/bsl\/1203350879","volume":"13","author":"N Segerlind","year":"2007","unstructured":"Segerlind, N.: The complexity of propositional proofs. Bulletin of Symbolic Logic 13(4), 417\u2013481 (2007)","journal-title":"Bulletin of Symbolic Logic"},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/s002220100188","volume":"147","author":"GM Ziegler","year":"2002","unstructured":"Ziegler, G.M.: Generalized Kneser coloring theorems with combinatorial proofs. Inventiones Mathematicae 147(3), 671\u2013691 (2002)","journal-title":"Inventiones Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T12:54:41Z","timestamp":1675860881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}