{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:47Z","timestamp":1763468087123,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_56","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"663-671","source":"Crossref","is-referenced-by-count":5,"title":["Extractors for Turing-Machine Sources"],"prefix":"10.1007","author":[{"given":"Emanuele","family":"Viola","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: The equivalence of sampling and searching. In: Computer Science Symp. in Russia (CSR), pp. 1\u201314 (2011)","DOI":"10.1007\/978-3-642-20712-9_1"},{"issue":"6","key":"56_CR2","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1137\/S009753979935476","volume":"32","author":"A. Ambainis","year":"2003","unstructured":"Ambainis, A., Schulman, L.J., Ta-Shma, A., Vazirani, U.V., Wigderson, A.: The quantum communication complexity of sampling. SIAM J. Comput.\u00a032(6), 1570\u20131585 (2003)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"56_CR3","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1137\/S0097539705447141","volume":"36","author":"B. Barak","year":"2006","unstructured":"Barak, B., Impagliazzo, R., Wigderson, A.: Extracting randomness using few independent sources. SIAM J. Comput.\u00a036(4), 1095\u20131118 (2006)","journal-title":"SIAM J. Comput."},{"key":"56_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. J.\u00a0of the ACM\u00a057(4) (2010)","DOI":"10.1145\/1734213.1734214"},{"key":"56_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Rao, A., Shaltiel, R., Wigderson, A.: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. In: ACM Symp.\u00a0on the Theory of Computing (STOC), pp. 671\u2013680 (2006)","DOI":"10.1145\/1132516.1132611"},{"key":"56_CR6","first-page":"42","volume":"19","author":"C. Beck","year":"2012","unstructured":"Beck, C., Impagliazzo, R., Lovett, S.: Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 42 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"56_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S1793042105000108","volume":"1","author":"J. Bourgain","year":"2005","unstructured":"Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. Int.\u00a0J.\u00a0of Number Theory (IJNT)\u00a01, 1\u201332 (2005)","journal-title":"Int.\u00a0J.\u00a0of Number Theory (IJNT)"},{"issue":"2","key":"56_CR8","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"B. Chor","year":"1988","unstructured":"Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J.\u00a0on Computing\u00a017(2), 230\u2013261 (1988)","journal-title":"SIAM J.\u00a0on Computing"},{"key":"56_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-22935-0_41","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. De","year":"2011","unstructured":"De, A., Watson, T.: Extractors and Lower Bounds for Locally Samplable Sources. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2011. LNCS, vol.\u00a06845, pp. 483\u2013494. Springer, Heidelberg (2011)"},{"issue":"4","key":"56_CR10","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1137\/S0097539705447049","volume":"36","author":"A. Gabizon","year":"2006","unstructured":"Gabizon, A., Raz, R., Shaltiel, R.: Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J.\u00a0on Computing\u00a036(4), 1072\u20131094 (2006)","journal-title":"SIAM J.\u00a0on Computing"},{"issue":"7","key":"56_CR11","doi-asserted-by":"publisher","first-page":"2761","DOI":"10.1137\/080722771","volume":"39","author":"O. Goldreich","year":"2010","unstructured":"Goldreich, O., Goldwasser, S., Nussboim, A.: On the implementation of huge random objects. SIAM J. Comput.\u00a039(7), 2761\u20132822 (2010)","journal-title":"SIAM J. Comput."},{"key":"56_CR12","doi-asserted-by":"crossref","unstructured":"Hennie, F.C.: Crossing sequences and off-line turing machine computations. In: Symposium on Switching Circuit Theory and Logical Design (SWCT) (FOCS), pp. 168\u2013172 (1965)","DOI":"10.1109\/FOCS.1965.5"},{"key":"56_CR13","unstructured":"Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Addison-Wesley Longman Publishing Co., Inc. (1969)"},{"key":"56_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: 26th ACM Symp.\u00a0on the Theory of Computing (STOC), pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"issue":"2-3","key":"56_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science\u00a043(2-3), 169\u2013188 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"56_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.jcss.2010.06.014","volume":"77","author":"J. Kamp","year":"2011","unstructured":"Kamp, J., Rao, A., Vadhan, S.P., Zuckerman, D.: Deterministic extractors for small-space sources. J. Comput. Syst. Sci.\u00a077(1), 191\u2013220 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"56_CR17","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"56_CR18","doi-asserted-by":"crossref","unstructured":"Li, X.: Improved constructions of three source extractors. In: IEEE Conf. \u00a0on Computational Complexity, CCC (2011)","DOI":"10.1109\/CCC.2011.26"},{"issue":"2","key":"56_CR19","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00037-012-0039-3","volume":"21","author":"S. Lovett","year":"2012","unstructured":"Lovett, S., Viola, E.: Bounded-depth circuits cannot sample good codes. Computational Complexity\u00a021(2), 245\u2013266 (2012)","journal-title":"Computational Complexity"},{"key":"56_CR20","doi-asserted-by":"crossref","unstructured":"Rao, A.: Extractors for low-weight affine sources. In: IEEE Conf.\u00a0on Computational Complexity (CCC), pp. 95\u2013101 (2009)","DOI":"10.1109\/CCC.2009.36"},{"key":"56_CR21","doi-asserted-by":"crossref","unstructured":"Raz, R.: Extractors with weak random seeds. In: ACM Symp.\u00a0on the Theory of Computing (STOC), pp. 11\u201320 (2005)","DOI":"10.1145\/1060590.1060593"},{"issue":"1","key":"56_CR22","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M. Santha","year":"1986","unstructured":"Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. J.\u00a0of Computer and System Sciences\u00a033(1), 75\u201387 (1986)","journal-title":"J.\u00a0of Computer and System Sciences"},{"issue":"2","key":"56_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.20207","volume":"33","author":"R. Shaltiel","year":"2008","unstructured":"Shaltiel, R.: How to get more mileage from randomness extractors. Random Struct. Algorithms\u00a033(2), 157\u2013186 (2008)","journal-title":"Random Struct. Algorithms"},{"key":"56_CR24","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: IEEE Symp.\u00a0on Foundations of Computer Science (FOCS), pp. 32\u201342 (2000)","DOI":"10.1109\/SFCS.2000.892063"},{"key":"56_CR25","doi-asserted-by":"crossref","unstructured":"Viola, E.: Extractors for circuit sources. In: IEEE Symp. \u00a0on Foundations of Computer Science, FOCS (2011)","DOI":"10.1109\/FOCS.2011.20"},{"issue":"1","key":"56_CR26","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/100814998","volume":"41","author":"E. Viola","year":"2012","unstructured":"Viola, E.: The complexity of distributions. SIAM J.\u00a0on Computing\u00a041(1), 191\u2013218 (2012)","journal-title":"SIAM J.\u00a0on Computing"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:24:27Z","timestamp":1743823467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}