{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:32Z","timestamp":1725665072288},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:22:34Z","timestamp":1330298554000},"page":"85-93","source":"Crossref","is-referenced-by-count":11,"title":["Super-bits, demi-bits, and NP\/qpoly-natural proofs"],"prefix":"10.1007","author":[{"given":"Steven","family":"Rudich","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13:850\u2013864, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR2","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0218037","volume":"18","author":"M. Furst","year":"1989","unstructured":"M. Furst and R. Kannan. Succinct certificates for almost all subset sum problems. Siam Journal on Computing, vol 18, 1989, pp. 550\u2013558.","journal-title":"Siam Journal on Computing"},{"issue":"4","key":"8_CR3","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792\u2013807, 1986.","journal-title":"Journal of the ACM"},{"issue":"4","key":"8_CR4","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"R. Impagliazzo and M. Naor. Efficient Cryptographic Schemes Provably as Secure as Subset Sum. Journal of Cryptology, 9(4):199\u2013216, 1996.","journal-title":"Journal of Cryptology"},{"doi-asserted-by":"crossref","unstructured":"J. Krajicek. Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge University Press, 1995.","key":"8_CR5","DOI":"10.1017\/CBO9780511529948"},{"unstructured":"J. Kraji\u010dek. Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic. Submitted to Journal of Symbolic Logic, 1994.","key":"8_CR6"},{"doi-asserted-by":"crossref","unstructured":"Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton University Press (1996).","key":"8_CR7","DOI":"10.1515\/9780691206844"},{"issue":"1","key":"8_CR8","first-page":"201","volume":"59","author":"A. Razborov","year":"1995","unstructured":"A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of Bounded Arithmetic, (Izvestiya of the RAN), 59(1):201\u2013222, 1995.","journal-title":"Izvestiya of the RAN"},{"key":"8_CR9","volume-title":"Technical Report RS-94-36","author":"A. Razborov","year":"1994","unstructured":"A. Razborov. On provably disjoint NP-pairs. Technical Report RS-94-36, Basic Research in Computer Science Center, Aarhus, Denmark, 1994."},{"doi-asserted-by":"crossref","unstructured":"A. Razborov and S. Rudich. Natural Proofs. 26th Annual Symposium on Theory of Computing (1994). To appear in special issue of JCSS.","key":"8_CR10","DOI":"10.1145\/195058.195134"},{"doi-asserted-by":"crossref","unstructured":"A. Yao. Theory and Applications of Trapdoor Functions. Proc. 23rd IEEE Symp. on Foundations of Computer Science, Chicago, IL (Nov. 1982), 80\u201391.","key":"8_CR11","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:43:22Z","timestamp":1619574202000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}