{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:57:48Z","timestamp":1759147068918},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600176"},{"type":"electronic","value":"9783540494041"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022253","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T01:12:29Z","timestamp":1132621949000},"page":"151-162","source":"Crossref","is-referenced-by-count":9,"title":["How to lie without being (easily) convicted and the lengths of proofs in propositional calculus"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Pudl\u00e1k","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel R.","family":"Buss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, The complexity of the pigeonhole principle, in Proceedings of the 29-th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 346\u2013355.","DOI":"10.1109\/SFCS.1988.21951"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Impagliazzo, J. Kraj\u00ed\u010dek, T. Pitassi, P. Pudl\u00e1k, and A. Woods, Exponential lower bounds for the pigeonhole principle, in Proceedings of the 24-th Annual ACM Symposium on Theory of Computing, 1992, pp. 200\u2013220.","DOI":"10.1145\/129712.129733"},{"key":"11_CR3","unstructured":"S. R. Buss, Bounded Arithmetic, Bibliopolis, 1986. Revision of 1985 Princeton University Ph.D. thesis."},{"key":"11_CR4","unstructured":"S. R. Buss and et al., Weak formal systems and connections to computational complexity. Student-written Lecture Notes for a Topics Course at U.C. Berkeley, January\u2013May 1988."},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"S. A. Cook, Feasibly constructive proofs and the propositional calculus, in Proceedings of the 7-th Annual ACM Symposium on Theory of Computing, 1975, pp. 83\u201397.","DOI":"10.1145\/800116.803756"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"S. A. Cook and R. A. Reckhow, On the lengths of proofs in the propositional calculus, preliminary version, in Proceedings of the Sixth Annual ACM Symposium on the Theory of Computing, 1974, pp. 135\u2013148.","DOI":"10.1145\/800119.803893"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. A. Cook","year":"1979","unstructured":"\u2014, The relative efficiency of propositional proof systems, Journal of Symbolic Logic, 44 (1979), pp. 36\u201350.","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"M. Dowd, Propositioned representation of arithmetic proofs, in Proceedings of the 10th ACM Symposium on Theory of Computing, 1978, pp. 246\u2013252.","DOI":"10.1145\/800133.804354"},{"key":"11_CR9","unstructured":"J. Kraj\u00ed\u010dek, Bounded Arithmetic, Propositional Calculus and Complexity Theory, Cambridge University Press, To appear."},{"key":"11_CR10","unstructured":"J. Kraj\u00ed\u010dek, Lower bounds to the size of constant-depth Frege proofs. To appear in Journal of Symbolic Logic."},{"key":"11_CR11","first-page":"137","volume":"30","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"\u2014 Speed-up for propositional Frege systems via generalizations of proofs, Commentationes Mathematicae Universitatis Carolinae, 30 (1989), pp. 137\u2013140.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"11_CR12","unstructured":"-, On Frege and extended Frege proof systems. Typeset manuscript, 1993."},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"J. Kraj\u00ed\u010dek and P. Pudl\u00e1k, Propositional proof systems, the consistency of first-order theories and the complexity of computations, Journal of Symbolic Logic, 54 (1989), pp. 1063\u20131079.","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1002\/malq.19900360106","volume":"36","author":"J. Kraj\u00ed\u010dek","year":"1990","unstructured":"\u2014, Quantified propositional calculi and fragments of bounded arithmetic, Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 36 (1990), pp. 29\u201346.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"11_CR15","first-page":"142","volume":"I","author":"V. P. Orevkov","year":"1980","unstructured":"V. P. Orevkov, On lower bounds on the lengths of proofs in propositional logic (russian), in Proc. of All Union Conference Metody matem. logiki v problemach iskusstvennogo intellekta i sistematicheskoje programmirovanie, Vilnius, vol. I, 1980, pp. 142\u2013144.","journal-title":"Proc. of All Union Conference Metody matem. logiki v problemach iskusstvennogo intellekta i sistematicheskoje programmirovanie, Vilnius"},{"key":"11_CR16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1090\/S0002-9947-1973-0432416-X","volume":"177","author":"R. Parikh","year":"1973","unstructured":"R. Parikh, Some results on the lengths of proofs, Transactions of the American Mathematical Society, 177 (1973), pp. 29\u201336.","journal-title":"Transactions of the American Mathematical Society"},{"key":"11_CR17","unstructured":"P. Pudl\u00e1k, The lengths of proofs. To appear in Handbook of Proof Theory, ed. S. Buss."},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"S. Riis, Independence in Bounded Arithmetic, PhD thesis, Oxford University, 1993.","DOI":"10.7146\/brics.v1i23.21644"},{"key":"11_CR19","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C. Shannon","year":"1949","unstructured":"C. Shannon, On the synthesis of two-terminal switching circuits, Bell System Technical Journal, 28 (1949), pp. 59\u201398.","journal-title":"Bell System Technical Journal"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022253","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T22:43:06Z","timestamp":1586558586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0022253","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}