{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T22:15:55Z","timestamp":1673388955794},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,12,19]],"date-time":"2008-12-19T00:00:00Z","timestamp":1229644800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1007\/s00453-008-9266-z","type":"journal-article","created":{"date-parts":[[2008,12,18]],"date-time":"2008-12-18T11:48:57Z","timestamp":1229600937000},"page":"134-156","source":"Crossref","is-referenced-by-count":2,"title":["Reconstructive Dispersers and Hitting Set Generators"],"prefix":"10.1007","volume":"55","author":[{"given":"Christopher","family":"Umans","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,12,19]]},"reference":[{"issue":"1","key":"9266_CR1","first-page":"179","volume":"45","author":"A.E. Andreev","year":"1998","unstructured":"Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P.: A new general derandomization method. J.\u00a0ACM 45(1), 179\u2013213 (1998)","journal-title":"J.\u00a0ACM"},{"issue":"6","key":"9266_CR2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1137\/S0097539797325636","volume":"28","author":"A.E. Andreev","year":"1999","unstructured":"Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P., Trevisan, L.: Weak random sources, hitting sets, and BPP simulations. SIAM J. Comput. 28(6), 179\u2013213 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9266_CR3","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"9266_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L.: One-sided versus two-sided error in probabilistic computation. In: Theoretical Aspects of Computer Science, 16th Annual Symposium, 1999","DOI":"10.1007\/3-540-49116-3_9"},{"issue":"3","key":"9266_CR5","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/s00037-005-0199-5","volume":"14","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Lee, T., van Melkebeek, D.: Language compression and pseudorandom generators. Comput. Complex. 14(3), 228\u2013255 (2005)","journal-title":"Comput. Complex."},{"key":"9266_CR6","unstructured":"Goldreich, O., Vadhan, S., Wigderson, A.: Simplified derandomization of BPP using a hitting set generator. Technical report TR00-004, Electronic Colloquium on Computational Complexity (January 2000)"},{"key":"9266_CR7","doi-asserted-by":"crossref","unstructured":"Guruswami, V.: Better extractors for better codes? In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 436\u2013444 (2004)","DOI":"10.1145\/1007352.1007422"},{"key":"9266_CR8","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sudan, M.: List decoding algorithms for certain concatenated codes. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000","DOI":"10.1145\/335305.335327"},{"issue":"3\u20134","key":"9266_CR9","first-page":"85","volume":"12","author":"D. Gutfreund","year":"2003","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games. Comput. Complex. 12(3\u20134), 85\u2013130 (2003)","journal-title":"Comput. Complex."},{"key":"9266_CR10","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P\u2009=\u2009BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"9266_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Near-optimal conversion of hardness into pseudo-randomness. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 181\u2013190 (1999)","DOI":"10.1109\/SFFCS.1999.814590"},{"key":"9266_CR12","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Extractors and pseudo-random generators with optimal seed-length. In: Proceedings of the Thirty-second Annual ACM Symposium on the Theory of Computing, May 2000, pp. 21\u201323","DOI":"10.1145\/335305.335306"},{"key":"9266_CR13","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Reducing the seed length in the Nisan-Wigderson generator. Full version of [11, 12]. Manuscript. Combinatorica (2003, to appear)"},{"key":"9266_CR14","first-page":"88","volume":"76","author":"V. Kabanets","year":"2002","unstructured":"Kabanets, V.: Derandomization: a brief overview. Bull. Eur. Assoc. Theor. Comput. Sci. 76, 88\u2013103 (2002)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"1\u20132","key":"9266_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1\u20132), 1\u201346 (2004)","journal-title":"Comput. Complex."},{"issue":"3","key":"9266_CR16","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/s00037-005-0197-7","volume":"14","author":"P.B. Miltersen","year":"2005","unstructured":"Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. Comput. Complex. 14(3), 256\u2013279 (2005)","journal-title":"Comput. Complex."},{"issue":"2","key":"9266_CR17","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., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9266_CR18","doi-asserted-by":"crossref","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 52(2), 172\u2013216 (2005)","journal-title":"J. ACM"},{"key":"9266_CR19","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M. Sudan","year":"1997","unstructured":"Sudan, M.: Decoding of Reed Solomon codes beyond the error-correction bound. J. Complex. 13, 180\u2013193 (1997)","journal-title":"J. Complex."},{"key":"9266_CR20","doi-asserted-by":"crossref","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.\u00a0Comput. Syst. Sci. 62, 236\u2013266 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"5","key":"9266_CR21","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/S0020-0190(02)00206-5","volume":"83","author":"A. Ta-Shma","year":"2002","unstructured":"Ta-Shma, A.: Storing information with extractors. Inf. Process. Lett. 83(5), 267\u2013274 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9266_CR22","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Umans, C., Zuckerman, D.: Loss-less condensers, unbalanced expanders, and extractors. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 143\u2013152 (2001)","DOI":"10.1145\/380752.380790"},{"issue":"12","key":"9266_CR23","doi-asserted-by":"crossref","first-page":"3015","DOI":"10.1109\/TIT.2004.838377","volume":"50","author":"A. Ta-Shma","year":"2004","unstructured":"Ta-Shma, A., Zuckerman, D.: Extractor codes. IEEE Trans. Inf. Theory 50(12), 3015\u20133025 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9266_CR24","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Zuckerman, D., Safra, S.: Extractors from Reed-Muller codes. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001","DOI":"10.1109\/SFCS.2001.959940"},{"issue":"4","key":"9266_CR25","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1145\/502090.502099","volume":"48","author":"L. Trevisan","year":"2002","unstructured":"Trevisan, L.: Extractors and pseudorandom generators. J. ACM 48(4), 860\u2013879 (2002)","journal-title":"J. ACM"},{"key":"9266_CR26","doi-asserted-by":"crossref","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. 67, 419\u2013440 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9266_CR27","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9266-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9266-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9266-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:03Z","timestamp":1559123103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9266-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,19]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9266"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9266-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,19]]}}}