{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:37:56Z","timestamp":1775054276958,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540614401","type":"print"},{"value":"9783540685807","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61440-0_142","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:38:08Z","timestamp":1330292288000},"page":"357-368","source":"Crossref","is-referenced-by-count":14,"title":["Hitting sets derandomize BPP"],"prefix":"10.1007","author":[{"given":"Alexander E.","family":"Andreev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea E. F.","family":"Clementi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 D. P.","family":"Rolim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Andreev A. (1995), \u201cThe complexity of nondeterministic functions\u201d, Information and Computation, to appear.","DOI":"10.7146\/brics.v1i2.21668"},{"key":"30_CR2","first-page":"319","volume":"1046","author":"A. Andreev","year":"1996","unstructured":"Andreev A., Clementi A., and Rolim J. (1996), \u201cOptimal Bounds on the Approximation of Boolean Functions, with Consequences on the Concept of Hardness\u201d, XIII Annual Symposium on Theoretical Aspects of Computer Science (STACS'96), LNCS, 1046, 319\u2013329. Also available via WWW in the electronic journal ECCC (TR95-041).","journal-title":"LNCS"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Andreev A., Clementi A., and Rolim J. (1996), \u201cHitting Sets Derandomize BPP\u201d (full version), submitted. Also available via WWW in the electronic journal ECCC (TR95-061).","DOI":"10.1007\/3-540-61440-0_142"},{"issue":"4","key":"30_CR4","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum M., and Micali S. (1984), \u201cHow to generate cryptographically strong sequences of pseudorandom bits\u201d, SIAM J. of Computing, 13(4), 850\u2013864.","journal-title":"SIAM J. of Computing"},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"Chor B., and O. Goldreich (1989), \u201cOn the Power of Two-Point Based Sampling\u201d, J. of Complexity, 5, 96\u2013106.","journal-title":"J. of Complexity"},{"key":"30_CR6","unstructured":"Karp R., Pippenger N., and Sipser M. (1982) \u201cTime-Randomness, Tradeoff\u201d, presented at AMS Conference on Probabilistic Computational Complexity."},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"Linial N., Luby M., Saks M., and Zuckerman D. (1993). \u201cEfficient construction of a small hitting set for combinatorial rectangles in high dimension\u201d, in Proc. 25th ACM STOC, 258\u2013267.","DOI":"10.1145\/167088.167166"},{"key":"30_CR8","unstructured":"Nisan N. (1990), Using Hard Problems to Create Pseudorandom Generators, ACM Distinguished Dissertation, MIT Press."},{"key":"30_CR9","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan N., and Wigderson A. (1994), \u201cHardness vs Randomness\u201d, J. Comput. System Sci. 49, 149\u2013167 (also presented at the 29th IEEE FOCS, 1988).","journal-title":"J. Comput. System Sci."},{"key":"30_CR10","first-page":"325","volume":"223","author":"M. Sipser","year":"1986","unstructured":"Sipser M. (1986), \u201cExpanders, Randomness or Time vs Space\u201d, in Proc. of 1st Conference on Structures in Complexity Theory, LNCS 223, 325\u2013329.","journal-title":"LNCS"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Wegener, I. (1987), The complexity of finite boolean functions, Wiley-Teubner Series in Computer Science.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Yao A. (1982), \u201cTheory and applications of trapdoor functions\u201d, in Proc. 23th IEEE FOCS, 80\u201391.","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\/3-540-61440-0_142.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:06:16Z","timestamp":1605647176000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61440-0_142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614401","9783540685807"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-61440-0_142","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}