{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:17Z","timestamp":1775282657073,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s00493-008-2259-3","type":"journal-article","created":{"date-parts":[[2008,7,31]],"date-time":"2008-07-31T14:58:14Z","timestamp":1217516294000},"page":"415-440","source":"Crossref","is-referenced-by-count":35,"title":["Deterministic extractors for affine sources over large fields"],"prefix":"10.1007","volume":"28","author":[{"given":"Ariel","family":"Gabizon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,7,31]]},"reference":[{"key":"2259_CR1","unstructured":"N. Alon: Tools from higher algebra, in: R. L. Graham, M. Gr\u00f6tschel and L. Lov\u00e1sz (eds.), Handbook of Combinatorics, Elsevier and The MIT Press, volume 2, pp. 1749\u20131783, 1995."},{"key":"2259_CR2","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1109\/FSCS.1990.89575","volume":"II","author":"N. Alon","year":"1990","unstructured":"N. Alon, O. Goldreich, J. H\u00e5stad and R. Peralta: Simple constructions of almost k-wise independent random variables, in: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, volume II, pages 544\u2013553, 1990.","journal-title":"Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science"},{"key":"2259_CR3","doi-asserted-by":"crossref","unstructured":"B. Barak, R. Impagliazzo and A. Wigderson: Extracting randomness from few independent sources, in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 384\u2013393, 2004.","DOI":"10.1109\/FOCS.2004.29"},{"key":"2259_CR4","doi-asserted-by":"crossref","unstructured":"B. Barak, G. Kindler, R. Shaltiel, B. Sudakov and A. Wigderson: Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors; in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (Baltimore, MD, USA), pp. 1\u201310, 2005.","DOI":"10.1145\/1060590.1060592"},{"key":"2259_CR5","doi-asserted-by":"crossref","unstructured":"M. Blum: Independent unbiased coin flips from a correlated biased source: a finite state Markov chain. in Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, pages 425\u2013433, 1984.","DOI":"10.1109\/SFCS.1984.715944"},{"issue":"1","key":"2259_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00039-007-0593-z","volume":"17","author":"J. Bourgain","year":"2007","unstructured":"J. Bourgain: On the construction of affine extractors, Geometric and Functional Analysis 17(1) (2007), 33\u201357.","journal-title":"Geometric and Functional Analysis"},{"issue":"2","key":"2259_CR7","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"B. Chor","year":"1988","unstructured":"B. Chor and O. Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing 17(2) (1988), 230\u2013261. Special issue on cryptography.","journal-title":"SIAM Journal on Computing"},{"key":"2259_CR8","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, J. H\u00e5stad, J. Friedman, S. Rudich and R. Smolensky: The bit extraction problem or t-resilient functions, in Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, 1985.","DOI":"10.1109\/SFCS.1985.55"},{"key":"2259_CR9","doi-asserted-by":"crossref","unstructured":"A. Cohen and A. Wigderson: Dispersers, deterministic amplification, and weak random sources, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"2259_CR10","doi-asserted-by":"crossref","unstructured":"Y. Dodis, A. Elbaz, R. Oliveira and R. Raz: Improved randomness extraction from two independent sources, in RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science. LNCS, 2004.","DOI":"10.1007\/978-3-540-27821-4_30"},{"key":"2259_CR11","unstructured":"A. Elbaz: Improved constructions for extracting quasi-random bits from sources of weak randomness, MSc Thesis, Weizmann Institute, 2003."},{"issue":"4","key":"2259_CR12","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1137\/S0097539705447049","volume":"36","author":"A. Gabizon","year":"2006","unstructured":"A. Gabizon, R. Raz and R. Shaltiel: Deterministic extractors for bit-fixing sources by obtaining an independent seed, SIAM Journal on Computing 36(4) (2006), 1072\u20131094.","journal-title":"SIAM Journal on Computing"},{"key":"2259_CR13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4153\/CMB-1971-007-1","volume":"14","author":"R. L. Graham","year":"1971","unstructured":"R. L. Graham and J. H. Spencer: A constructive solution to a tournament problem, Canad. Math. Bull. 14 (1971), 45\u201348.","journal-title":"Canad. Math. Bull."},{"key":"2259_CR14","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1090\/S0002-9947-1963-0143712-1","volume":"106","author":"A. Hales","year":"1963","unstructured":"A. Hales and R. Jewett: Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222\u2013229.","journal-title":"Trans. Amer. Math. Soc."},{"key":"2259_CR15","doi-asserted-by":"crossref","unstructured":"J. Kamp and D. Zuckerman: Deterministic extractors for bit-fixing sources and exposure-resilient cryptography, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.","DOI":"10.1109\/SFCS.2003.1238184"},{"key":"2259_CR16","doi-asserted-by":"crossref","unstructured":"M. Naor, A. Nussboim and E. Tromer: Efficiently constructible huge graphs that preserve first order properties of random graphs, in TCC, pages 66\u201385, 2005.","DOI":"10.1007\/978-3-540-30576-7_5"},{"issue":"1","key":"2259_CR17","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1006\/jcss.1997.1546","volume":"58","author":"N. Nisan","year":"1999","unstructured":"N. Nisan and A. Ta-Shma: Extracting randomness: A survey and new constructions, Journal of Computer and System Sciences 58(1) (1999), 148\u2013173.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2259_CR18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"N. Nisan and D. Zuckerman: Randomness is linear in space, Journal of Computer and System Sciences 52(1) (1996), 43\u201352.","journal-title":"Journal of Computer and System Sciences"},{"key":"2259_CR19","doi-asserted-by":"crossref","unstructured":"N. Nisan: Extracting randomness: How and why: A survey, in Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pages 44\u201358, 1996.","DOI":"10.1109\/CCC.1996.507667"},{"key":"2259_CR20","doi-asserted-by":"crossref","unstructured":"R. Raz: Extractors with weak random seeds, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (Baltimore, MD, USA), pp. 11\u201320, 2005.","DOI":"10.1145\/1060590.1060593"},{"issue":"1","key":"2259_CR21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1006\/jcss.2002.1824","volume":"65","author":"R. Raz","year":"2002","unstructured":"R. Raz, O. Reingold and S. Vadhan: Extracting all the randomness and reducing the error in trevisan\u2019s extractors, Journal of Computer and System Sciences 65(1) (2002), 97\u2013128.","journal-title":"Journal of Computer and System Sciences"},{"key":"2259_CR22","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M. Santha","year":"1986","unstructured":"M. Santha and U. V. Vazirani: Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences 33 (1986), 75\u201387.","journal-title":"Journal of Computer and System Sciences"},{"key":"2259_CR23","doi-asserted-by":"crossref","unstructured":"W. M. Schmidt: Equations over Finite Fields: An Elementary Approach, Lecture Notes in Mathematics, volume 536, Springer-Verlag, 1976.","DOI":"10.1007\/BFb0080437"},{"key":"2259_CR24","first-page":"67","volume":"77","author":"R. Shaltiel","year":"2002","unstructured":"R. Shaltiel: Recent developments in explicit constructions of extractors, Bulletin of the EATCS 77 (2002), 67\u201395.","journal-title":"Bulletin of the EATCS"},{"key":"2259_CR25","doi-asserted-by":"crossref","unstructured":"R. Shaltiel: How to get more mileage from randomness extractors, in IEEE Conference on Computational Complexity, pages 46\u201360, 2006.","DOI":"10.1109\/CCC.2006.24"},{"issue":"2","key":"2259_CR26","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"R. Shaltiel","year":"2005","unstructured":"R. Shaltiel and Ch. Umans: Simple extractors for all min-entropies and a new pseudorandom generator, J. ACM 52(2) (2005), 172\u2013216.","journal-title":"J. ACM"},{"issue":"5","key":"2259_CR27","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1016\/j.jcss.2005.05.010","volume":"72","author":"A. Ta-Shma","year":"2006","unstructured":"A. Ta-Shma, D. Zuckerman and S. Safra: Extractors from reed-muller codes, Journal of Computer and System Sciences 72(5) (2006), 786\u2013812.","journal-title":"Journal of Computer and System Sciences"},{"key":"2259_CR28","doi-asserted-by":"crossref","unstructured":"L. Trevisan: Construction of extractors using pseudorandom generators, in Proceedings of the 31st ACM Symposium on Theory of Computing, 1999.","DOI":"10.1145\/301250.301289"},{"key":"2259_CR29","doi-asserted-by":"crossref","unstructured":"L. Trevisan and S. Vadhan: Extracting randomness from samplable distributions, in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000.","DOI":"10.1109\/SFCS.2000.892063"},{"key":"2259_CR30","doi-asserted-by":"crossref","unstructured":"S. Vadhan: Randomness extractors and their many guises, in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 9\u201312, 2002.","DOI":"10.1109\/SFCS.2002.1181877"},{"key":"2259_CR31","doi-asserted-by":"crossref","unstructured":"U. Vazirani: Efficient considerations in using semi-random sources, in Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, 1987.","DOI":"10.1145\/28395.28413"},{"issue":"4","key":"2259_CR32","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/BF02579325","volume":"7","author":"U. Vazirani","year":"1987","unstructured":"U. Vazirani: Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica 7(4) (1987), 375\u2013392.","journal-title":"Combinatorica"},{"key":"2259_CR33","unstructured":"U. Vazirani and V. Vazirani: Random polynomial time is equal to semi-random polynomial time, Technical Report TR88-959, Cornell University, Computer Science Department, December 1988."},{"key":"2259_CR34","first-page":"36","volume":"12","author":"J. Neumann VON","year":"1951","unstructured":"J. VON Neumann: Various techniques used in connection with random digits, Applied Math Series 12 (1951), 36\u201338.","journal-title":"Applied Math Series"},{"key":"2259_CR35","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1073\/pnas.34.5.204","volume":"34","author":"A. Weil","year":"1948","unstructured":"A. Weil: On some exponential sums, in Proc. Nat. Acad. Sci. USA, volume 34, pages 204\u2013207, 1948.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"2259_CR36","doi-asserted-by":"crossref","unstructured":"D. Zuckerman: General weak random sources, in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 534\u2013543, 1990.","DOI":"10.1109\/FSCS.1990.89574"},{"issue":"4\/5","key":"2259_CR37","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01940870","volume":"16","author":"D. Zuckerman","year":"1996","unstructured":"D. Zuckerman: Simulating BPP using a general weak random source, Algorithmica 16(4\/5) (1996), 367\u2013391.","journal-title":"Algorithmica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-008-2259-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-008-2259-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-008-2259-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T08:00:20Z","timestamp":1738310420000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-008-2259-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["2259"],"URL":"https:\/\/doi.org\/10.1007\/s00493-008-2259-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]}}}