{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T05:20:21Z","timestamp":1736572821120,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540647812"},{"type":"electronic","value":"9783540686811"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055054","type":"book-chapter","created":{"date-parts":[[2006,8,1]],"date-time":"2006-08-01T12:08:05Z","timestamp":1154434085000},"page":"212-214","source":"Crossref","is-referenced-by-count":1,"title":["Do probabilistic algorithms outperform deterministic ones?"],"prefix":"10.1007","author":[{"given":"Avi","family":"Wigderson","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"A. Andreev, A. Clementi and J. Rolim, \u201cHitting Sets Derandomize BPP\u201d, in XXIII International Colloquium on Algorithms, Logic and Programming (ICALP'96), 1996.","DOI":"10.1007\/3-540-61440-0_142"},{"key":"19_CR2","unstructured":"A. Andreev, A. Clementi, and J. Rolim, \u201cHitting Properties of Hard Boolean Operators and its Consequences on BPP\u201d, manuscript, 1996."},{"key":"19_CR3","first-page":"307","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan and A. Wigderson, \u201cBPP has Subexponential Time Simulations unless EXPTIME has Publishablc Proofs\u201d, Complexity Theory, Vol 3, pp. 307\u2013318, 1993.","journal-title":"Complexity Theory"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali. \u201cHow to Generate Cryptographically Strong Sequences of Pseudo-Random Bits\u201d, SIAM J. Comput., Vol. 13, pages 850\u2013864, 1984.","journal-title":"SIAM J. Comput."},{"key":"19_CR5","unstructured":"O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, to be. published by Springer."},{"key":"19_CR6","first-page":"377","volume-title":"The. Universal Turing Machine: A Half-Century Survey","author":"O. Goldreich","year":"1988","unstructured":"O. Goldreich, \u201cRandomness, Interaction, Proofs and Zero-Knowledge\u201d, The. Universal Turing Machine: A Half-Century Survey, R. Herken (ed.), Oxford University Press, 1988, London, pp. 377\u2013406. A revised version of the section on pseudorandomness is available from http:\/\/theory.lcs.mit.edu\/pub\/people\/oded\/prg88.ps."},{"key":"19_CR7","unstructured":"O. Goldreich. \u201cPseudorandomness\u201d, Chapter 3 of Foundation of Cryptography \u2014 Fragments of a Book, February 1995. Available from http:\/\/theory.lcs.mit.edu\/~oded\/frag.html."},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L.A. Levin. \u201cA Hard-Core Predicate for all One-Way Functions\u201d, in ACM Symp. on Theory of Computing, pp. 25\u201332, 1989.","DOI":"10.1145\/73007.73010"},{"key":"19_CR9","unstructured":"J. Hastad, R. Impagliazzo, L.A. Levin and M. Luby, \u201cConstruction of Pseudorandom Generator from any One-Way Function\u201d, to appear in SICOMP. (See. preliminary versions by Impagliazzo el., al. in 21st STOC and Hastad in 22nd STOC.)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"It. Impagliazzo, \u201cHard-core Distributions for Somewhat Hard Problems\u201d, in 36th FOCS, pages 538\u2013545, 1995.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and A. Wigderson, \u201cP=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma\u201d, in 29th STOC, pp. 220\u2013229, 1997.","DOI":"10.1145\/258533.258590"},{"key":"19_CR12","unstructured":"R. Impagliazzo and A. Wigderson, \u201cA Gap Theorem for Derandomization\u201d, In preparation."},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L.A. Levin","year":"1986","unstructured":"L.A. Levin, \u201cAverage Case Complete Problems\u201d, SIAM J. Comput., 15:285\u2013286, 1986.","journal-title":"SIAM J. Comput."},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"M. Luby, Pseudorandomness and Cryptographic Applications, Princeton Computer Science Notes, Princeton University Press, 1996.","DOI":"10.1515\/9780691206844"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"R. Lipton, \u201cNow directions in testing\u201d, In J. Fegenbaum and M. Merritt, editors, Distributed Computing and Cryptography, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 2, pp. 191\u2013202. American Mathematical Society, 1991.","DOI":"10.1090\/dimacs\/002\/13"},{"issue":"1","key":"19_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"N. Nisan","year":"1991","unstructured":"N. Nisan, \u201cPseudo-random bits for constant depth circuits\u201d, Combinatorica 11 (1), pp. 63\u201370, 1991.","journal-title":"Combinatorica"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan, and A. Wigderson, \u201cHardness vs Randomness\u201d, J. Comput. System Sci. 49, 149\u2013167, 1994","journal-title":"J. Comput. System Sci."},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"A. Shamir, \u201cOn the generation of cryptographically strong pseudo-random sequences\u201d, 8th ICALP, Lecture Notoes in Computer Science 62, Springer-Verlag, pp. 544\u2013550, 1981.","DOI":"10.1007\/3-540-10843-2_43"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"A.C. Yao, \u201cTheory and Application of Trapdoor Functions\u201d, in 23st FOCS, pages 80\u201391, 1982.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T07:59:47Z","timestamp":1736495987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540647812","9783540686811"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0055054","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}