{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T14:28:19Z","timestamp":1774880899190,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540634379","type":"print"},{"value":"9783540695479","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0029951","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T06:24:59Z","timestamp":1133418299000},"page":"85-90","source":"Crossref","is-referenced-by-count":7,"title":["Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus"],"prefix":"10.1007","author":[{"given":"Jan","family":"Kraji\u010dek","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1112\/plms\/s3-73.1.1","volume":"73","author":"P. Beame","year":"1996","unstructured":"Beame, P., Impagliazzo, R., Kraj\u00ed\u010dek, J., Pitassi, T., Pudl\u00e1k, P.: Lower bounds on Hilbert's Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society 73(3) (1996) 1\u201326","journal-title":"Proceedings of the London Mathematical Society"},{"key":"8_CR2","unstructured":"Beame, P., Riis, S.: More on the relative strength of counting principles. (submitted)"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Buss, S., Impagliazzo, R., Kraji\u010dek, J., Pudl\u00e1k, P., Razborov, A. A., Sgall, J.: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity (to appear)","DOI":"10.1007\/BF01294258"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Clegg, M, Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the 28th ACM Symposium on Theory of Computing, ACM (1996) 174\u2013183","DOI":"10.1145\/237814.237860"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Kraj\u0129cek, J.: Bounded arithmetic, propositional logic, and complexity theory. Encyclopedia of Mathematics and Its Applications, Vol. 60 Cambridge University Press (1995)","DOI":"10.1017\/CBO9780511529948"},{"key":"8_CR6","first-page":"56","volume":"2","author":"J. Kraji\u0107ek","year":"1995","unstructured":"Kraji\u0107ek, J.: A fundamental problem of mathematical logic. Annals of the Kurt G\u00f6del Society, Springer-Verlag, Collegium Logicum, 2 (1995) 56\u201364","journal-title":"Annals of the Kurt G\u00f6del Society, Springer-Verlag, Collegium Logicum"},{"key":"8_CR7","series-title":"Synthese Library","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-94-017-0487-8_4","volume-title":"Logic and Scientific Methods","author":"J. Kraji\u0107ek","year":"1997","unstructured":"Kraji\u0107ek, J.: On methods for proving lower bounds in propositional logic. In: Logic and Scientific Methods Eds. M. L. Dalla Chiara et al., (Vol. 1 of Proc. of the Tenth International Congress of Logic, Methodology and Philosophy of Science, Florence (August 19\u201325, 1995)), Synthese Library, 259 Kluwer Academic Publ., Dordrecht (1997) 69\u201383"},{"key":"8_CR8","unstructured":"Kraji\u0107ek, J.: On the degree of ideal membership proofs from uniform families of polynomials over a finite field. (in preparation)"},{"issue":"1","key":"8_CR9","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J. Kraji\u0107ek","year":"1995","unstructured":"Kraji\u0107ek, J.,Pudl\u00e1k, P., Woods, A.: Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures and Algorithms 7(1) (1995) 15\u201339","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T. Pitassi","year":"1993","unstructured":"Pitassi, T., Beame, P., and Impagliazzo, R.: Exponential lower bounds for the pigeonhole principle. Computational Complexity 3(2) (1993) 97\u2013140","journal-title":"Computational Complexity"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Pudl\u00e1k, P.: The lengths of proofs. In: Handbook of Proof Theory, Ed. S. Buss, (to appear)","DOI":"10.1016\/S0049-237X(98)80023-2"},{"key":"8_CR12","unstructured":"Razborov, A. A.: Lower bounds for propositional proofs and independence results in bounded arithmetic. In: Proc. of the 23rd ICALP, F.Meyer auf der Heide and B. Monien eds., LN in Computer Science, 1099, Springer-Verlag, (1996) 48\u201362"},{"key":"8_CR13","unstructured":"Razborov, A. A.: Lower bounds for the polynomial calculus. (submitted)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1997"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:22:09Z","timestamp":1586593329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634379","9783540695479"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0029951","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}