{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:37:05Z","timestamp":1770982625778,"version":"3.50.1"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":4703,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2001,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider tautologies formed from a pseudo-random number generator, defined in Kraj\u00ed\u010dek [11] and in Alekhnovich et al. [2]. We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic formulated in Kraj\u00ed\u010dek [11]. Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture.<\/jats:p>","DOI":"10.2307\/2687774","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T07:17:03Z","timestamp":1146986223000},"page":"197-212","source":"Crossref","is-referenced-by-count":23,"title":["Tautologies from Pseudo-Random Generators"],"prefix":"10.1017","volume":"7","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600005813_ref031","first-page":"115","volume-title":"Studies in mathematics and mathematical logic, part II","author":"Tseitin","year":"1968"},{"key":"S1079898600005813_ref001","first-page":"346","volume-title":"Proceedings of the IEEE 29th annual symposium on foundation of computer science","author":"Ajtai","year":"1988"},{"key":"S1079898600005813_ref028","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"S1079898600005813_ref017","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"S1079898600005813_ref020","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2674"},{"key":"S1079898600005813_ref002","unstructured":"Alekhnovich M. , Ben-Sasson E. , Razborov A. A. , and Wigderson A. , Pseudorandom generators in propositional proof complexity, preprint, 03 2000."},{"key":"S1079898600005813_ref025","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028061"},{"key":"S1079898600005813_ref013","doi-asserted-by":"publisher","DOI":"10.2307\/2275250"},{"key":"S1079898600005813_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_10"},{"key":"S1079898600005813_ref014","volume-title":"Encyclopedia of mathematics and its applications","volume":"60","author":"Kraj\u00ed\u010dek","year":"1995"},{"key":"S1079898600005813_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"S1079898600005813_ref005","first-page":"151","volume-title":"Proceedings of the 3rd annual ACM symposium on theory of computing","author":"Cook","year":"1971"},{"key":"S1079898600005813_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"S1079898600005813_ref027","volume-title":"Handbook of proof theory","author":"Pudl\u00e1k","year":"1997"},{"key":"S1079898600005813_ref012","first-page":"137","article-title":"Speed-up for propositional Frege systems via generalizations of proofs","volume":"30","author":"Kraj\u00ed\u010dek","year":"1989","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"S1079898600005813_ref011","unstructured":"Kraj\u00ed\u010dek J. , On the weak pigeonhole principle, to appear in Fundamenta Mathematicae (preprint on web 08 9 '99)."},{"key":"S1079898600005813_ref006","first-page":"83","volume-title":"Proceedings of the 7th annual ACM symposium on theory of computing","author":"Cook","year":"1975"},{"key":"S1079898600005813_ref007","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"S1079898600005813_ref018","first-page":"193","volume-title":"Computer science logic, October 1989","volume":"440","author":"Kraj\u00ed\u010dek","year":"1990"},{"key":"S1079898600005813_ref008","doi-asserted-by":"crossref","unstructured":"Dowd M. , Propositional representations of arithmetic proofs, Ph.D. thesis , University of Toronto, 1979.","DOI":"10.1145\/800133.804354"},{"key":"S1079898600005813_ref030","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"S1079898600005813_ref004","first-page":"24","volume-title":"Proceedings of logic, methodology and philosophy of science","author":"Cobham","year":"1965"},{"key":"S1079898600005813_ref029","first-page":"201","article-title":"Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic","volume":"59","author":"Razborov","year":"1995","journal-title":"Rossi\u00eeskaya Akademiya Nauk. Izvestiya. Seriya Matematicheskaya"},{"key":"S1079898600005813_ref003","unstructured":"Buss S. R. , Bounded arithmetic, Bibliopolis, Naples, 1986, Revision of 1985 Princeton University Ph.D. thesis."},{"key":"S1079898600005813_ref016","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"S1079898600005813_ref023","doi-asserted-by":"crossref","unstructured":"Maciel A. , Pitassi T. , and Woods A. , A new proof of the weak pigeonhole principle, preprint, 1999.","DOI":"10.1145\/335305.335348"},{"key":"S1079898600005813_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2822-6_19"},{"key":"S1079898600005813_ref033","first-page":"92","volume-title":"Proceedings of the 23rd annual symposium on foundation of computer science","author":"Yao","year":"1982"},{"key":"S1079898600005813_ref021","first-page":"48","volume-title":"Mathematical foundations of computer science","volume":"452","author":"Kraj\u00ed\u010dek","year":"1990"},{"key":"S1079898600005813_ref032","first-page":"425","volume":"1","author":"Urquhart","year":"1995","journal-title":"The complexity of propositional proofs"},{"key":"S1079898600005813_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"S1079898600005813_ref010","first-page":"220","volume-title":"Proceedings of the 29th annual ACM symposium on theory of computing","author":"Impagliazzo","year":"1997"},{"key":"S1079898600005813_ref019","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600005813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T00:16:08Z","timestamp":1557274568000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600005813\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,3]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,6]]}},"alternative-id":["S1079898600005813"],"URL":"https:\/\/doi.org\/10.2307\/2687774","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,3]]}}}