{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:47:53Z","timestamp":1725587273554},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_53","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"630-641","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Bounded-Depth Frege Is Not Optimal"],"prefix":"10.1007","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Galesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Razborov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"53_CR1","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1137\/06066850X","volume":"38","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich, M., Razborov, A.A.: Resolution is not automatizable unless W(P) is tractable. SIAM Journal on Computing\u00a038(4), 1347\u20131363 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"53_CR2","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00037-007-0230-0","volume":"16","author":"P. Beame","year":"2007","unstructured":"Beame, P., Impagliazzo, R., Sabharwal, A.: The resolution complexity of independent sets and vertex covers in random graphs. Computational Complexity\u00a016(3), 245\u2013297 (2007)","journal-title":"Computational Complexity"},{"issue":"4","key":"53_CR3","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1137\/S0097539700369156","volume":"31","author":"P. Beame","year":"2002","unstructured":"Beame, P., Karp, R.M., Pitassi, T., Saks, M.E.: The efficiency of resolution and Davis\u2013Putnam procedures. SIAM J. Comput.\u00a031(4), 1048\u20131075 (2002)","journal-title":"SIAM J. Comput."},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"Beyersdorff, O., Galesi, N., Lauria, M.: Parameterized complexity of DPLL search procedures. In: Proc. 14th International Conference on Theory and Applications of Satisfiability Testing (to appear, 2011)","DOI":"10.1007\/978-3-642-21581-0_3"},{"issue":"3","key":"53_CR5","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"},{"key":"53_CR6","doi-asserted-by":"publisher","first-page":"916","DOI":"10.2307\/2273826","volume":"52","author":"S.R. Buss","year":"1987","unstructured":"Buss, S.R.: Polynomial size proofs of the propositional pigeonhole principle. The Journal of Symbolic Logic\u00a052, 916\u2013927 (1987)","journal-title":"The Journal of Symbolic Logic"},{"issue":"1","key":"53_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.apal.2007.09.003","volume":"151","author":"Y. Chen","year":"2008","unstructured":"Chen, Y., Flum, J.: The parameterized complexity of maximality and minimality problems. Annals of Pure and Applied Logic\u00a0151(1), 22\u201361 (2008)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"53_CR8","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.A.: The relative efficiency of propositional proof systems. The Journal of Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"Dantchev, S.S., Martin, B., Szeider, S.: Parameterized proof complexity. In: Proc. 48th IEEE Symposium on the Foundations of Computer Science, pp. 150\u2013160 (2007)","DOI":"10.1109\/FOCS.2007.53"},{"key":"53_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"2","key":"53_CR11","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0890-5401(03)00161-5","volume":"187","author":"J. Flum","year":"2003","unstructured":"Flum, J., Grohe, M.: Describing parameterized complexity classes. Information and Computation\u00a0187(2), 291\u2013319 (2003)","journal-title":"Information and Computation"},{"key":"53_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"14","key":"53_CR13","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1016\/j.artint.2009.06.005","volume":"173","author":"Y. Gao","year":"2009","unstructured":"Gao, Y.: Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability. Artificial Intelligence\u00a0173(14), 1343\u20131366 (2009)","journal-title":"Artificial Intelligence"},{"key":"53_CR14","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, 297\u2013308 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"53_CR15","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Woods, A.: Exponential lower bounds to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures and Algorithms\u00a07(1), 15\u201339 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"53_CR16","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"53_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T. Pitassi","year":"1993","unstructured":"Pitassi, T., Beame, P., Impagliazzo, R.: Exponential lower bounds for the pigeonhole principle. Computational Complexity\u00a03, 97\u2013140 (1993)","journal-title":"Computational Complexity"},{"issue":"3","key":"53_CR18","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 planes proofs and monotone computations. The Journal of Symbolic Logic\u00a062(3), 981\u2013998 (1997)","journal-title":"The Journal of Symbolic Logic"},{"issue":"4","key":"53_CR19","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s00493-002-0007-7","volume":"22","author":"A. Razborov","year":"2002","unstructured":"Razborov, A., Wigderson, A., Yao, A.: Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Combinatorica\u00a022(4), 555\u2013574 (2002)","journal-title":"Combinatorica"},{"issue":"3","key":"53_CR20","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00037-001-8194-y","volume":"10","author":"S. Riis","year":"2001","unstructured":"Riis, S.: A complexity gap for tree resolution. Computational Complexity\u00a010(3), 179\u2013209 (2001)","journal-title":"Computational Complexity"}],"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-22006-7_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T02:58:26Z","timestamp":1553828306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}