{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:02:19Z","timestamp":1750492939586,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_12","type":"book-chapter","created":{"date-parts":[[2006,11,28]],"date-time":"2006-11-28T04:48:02Z","timestamp":1164689282000},"page":"105-116","source":"Crossref","is-referenced-by-count":3,"title":["On Obtaining Pseudorandomness from Error-Correcting Codes"],"prefix":"10.1007","author":[{"given":"Shankar","family":"Kalyanaraman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Umans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"Andreev, A.E., Baskakov, J.L., Clementi, A.E.F., Rolim, J.D.P.: Small random sets for affine spaces and better explicit lower bounds for branching programs. Technical Report TR04-053, ECCC (1997)"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Struct. Algorithms\u00a0(3), 289\u2013304 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bogdanov, A.: Pseudorandom generators for low degree polynomials. In: Proceedings of STOC, pp. 21\u201330 (2005)","DOI":"10.1145\/1060590.1060594"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Shpilka, A.: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In: Proceedings of STOC, pp. 592\u2013601 (2005)","DOI":"10.1145\/1060590.1060678"},{"key":"12_CR5","unstructured":"Goldreich, O., Zuckerman, D.: Another proof that BPP subseteq PH (and more). Technical Report TR97-045, ECCC (1997)"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proceedings of STOC, pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds\u00a013, 1\u201346 (2004)","DOI":"10.1007\/s00037-004-0182-6"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Klivans, A., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings of STOC, pp. 216\u2013223 (2001)","DOI":"10.1145\/380752.380801"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Lu, C.-J., Reingold, O., Vadhan, S., Wigderson, A.: Extractors: optimal up to constant factors. In: Proceedings of STOC, pp. 602\u2013611 (2003)","DOI":"10.1145\/780542.780630"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Lewin, D., Vadhan, S.: Checking polynomial identities over any field: Towards a derandomization? In: Proceedings of STOC, pp. 438\u2013447 (1998)","DOI":"10.1145\/276698.276856"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1016\/S0022-0000(02)00022-3","volume":"65","author":"E. Mossel","year":"2002","unstructured":"Mossel, E., Umans, C.: On the complexity of approximating the VC dimension. J. Comput. Syst. Sci.\u00a065(4), 660\u2013671 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012, 249\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"1","key":"12_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01205052","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N.: RL\u2009\u2286\u2009SC. Computational Complexity\u00a04(1), 1\u201311 (1994)","journal-title":"Computational Complexity"},{"issue":"4","key":"12_CR14","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SICOMP\u00a022(4), 838\u2013856 (1993)","journal-title":"SICOMP"},{"issue":"1","key":"12_CR15","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci.\u00a052(1), 43\u201352 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non-commutative models. In: CCC","DOI":"10.1109\/CCC.2004.1313845"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Reingold, O., Shaltiel, R., Wigderson, A.: Extracting randomness via repeated condensing. In: IEEE (ed.) FOCS, pp. 22\u201331 (2000)","DOI":"10.1109\/SFCS.2000.892008"},{"issue":"4","key":"12_CR18","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1006\/jcss.2001.1776","volume":"63","author":"A. Russell","year":"2001","unstructured":"Russell, A., Zuckerman, D.: Perfect information leader election in log* n\u2009+\u2009O(1) rounds. J. Comput. Syst. Sci.\u00a063(4), 612\u2013626 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR19","first-page":"67","volume":"77","author":"R. Shaltiel","year":"2002","unstructured":"Shaltiel, R.: Recent developments in explicit constructions of extractors. Bulletin of EATCS\u00a077, 67\u201395 (2002); Columns: Computational Complexity","journal-title":"Bulletin of EATCS"},{"issue":"3","key":"12_CR20","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0022-0000(88)90035-9","volume":"36","author":"M. Sipser","year":"1988","unstructured":"Sipser, M.: Expanders, randomness, or time versus space. J. Comput. Syst. Sci.\u00a036(3), 379\u2013383 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR21","first-page":"67","volume":"70","author":"A. Srinivasan","year":"2000","unstructured":"Srinivasan, A.: Low-discrepancy sets for high-dimensional rectangles: a survey. Bulletin of the EATCS\u00a070, 67\u201376 (2000)","journal-title":"Bulletin of the EATCS"},{"issue":"2","key":"12_CR22","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci.\u00a062(2), 236\u2013266 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"12_CR23","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"R. Shaltiel","year":"2005","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM\u00a052(2), 172\u2013216 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"12_CR24","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1006\/jcss.1998.1616","volume":"58","author":"M. Saks","year":"1999","unstructured":"Saks, M., Zhou, S.: BPSPACE(S) \u2286 DSPACE(S 3\/2). J. Comput. Syst. Sci.\u00a058(2), 376\u2013403 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"12_CR25","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1145\/502090.502099","volume":"48","author":"L. Trevisan","year":"2001","unstructured":"Trevisan, L.: Extractors and pseudorandom generators. J. ACM\u00a048(4), 860\u2013879 (2001)","journal-title":"J. ACM"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Zuckerman, D.: Extractor codes. In: ACM (ed.) Proceedings of STOC, pp. 193\u2013199 (2001)","DOI":"10.1145\/380752.380800"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Zuckerman, D., Safra, S.: Extractors from Reed-Muller codes. In: Proceedings of FOCS, pp. 638\u2013647 (2001)","DOI":"10.1109\/SFCS.2001.959940"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Umans, C.: Hardness of approximating $\\Sigma_{2}^{p}$ minimization problems. In: Proceedings of FOCS, pp. 465\u2013474 (1999)","DOI":"10.1109\/SFFCS.1999.814619"},{"issue":"2","key":"12_CR29","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/S0022-0000(03)00046-1","volume":"67","author":"C. Umans","year":"2003","unstructured":"Umans, C.: Pseudo-random generators for all hardnesses. J. Comput. Syst. Sci.\u00a067(2), 419\u2013440 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Wigderson, A., Zuckerman, D.: Expanders that beat the eigenvalue bound: Explicit construction and applications. In: Proceedings of STOC, pp. 245\u2013251 (1993)","DOI":"10.1145\/167088.167163"},{"key":"12_CR31","first-page":"80","volume-title":"Proceedings of the 23rd Symposium on Foundations of Computer Science (FOCS)","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd Symposium on Foundations of Computer Science (FOCS), pp. 80\u201391. IEEE Computer Society Press, Los Alamitos (1982)"},{"issue":"6","key":"12_CR32","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1137\/S0097539794266407","volume":"25","author":"D. Zuckerman","year":"1996","unstructured":"Zuckerman, D.: On unapproximable versions of NP -complete problems. SICOMP\u00a025(6), 1293\u20131304 (1996)","journal-title":"SICOMP"},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"D. Zuckerman","year":"1997","unstructured":"Zuckerman, D.: Randomness-optimal oblivious sampling. Random Struct. Algorithms\u00a011, 345\u2013367 (1997)","journal-title":"Random Struct. Algorithms"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T05:02:42Z","timestamp":1736658162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11944836_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}