Abstract
We obtain the first deterministic randomness extractors for n-bit sources with min-entropy ≥ n 1 − α generated (or sampled) by single-tape Turing machines running in time n 2 − 16 α, for all sufficiently small α > 0. We also show that such machines cannot sample a uniform n-bit input to the Inner Product function together with the output.
The proofs combine a variant of the crossing-sequence technique by Hennie [SWCT 1965] with extractors for block sources, especially those by Chor and Goldreich [SICOMP 1988] and by Kamp, Rao, Vadhan, and Zuckerman [JCSS 2011].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Aaronson, S.: The equivalence of sampling and searching. In: Computer Science Symp. in Russia (CSR), pp. 1–14 (2011)
Ambainis, A., Schulman, L.J., Ta-Shma, A., Vazirani, U.V., Wigderson, A.: The quantum communication complexity of sampling. SIAM J. Comput. 32(6), 1570–1585 (2003)
Barak, B., Impagliazzo, R., Wigderson, A.: Extracting randomness using few independent sources. SIAM J. Comput. 36(4), 1095–1118 (2006)
Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. J. of the ACM 57(4) (2010)
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. on the Theory of Computing (STOC), pp. 671–680 (2006)
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) 19, 42 (2012)
Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. Int. J. of Number Theory (IJNT) 1, 1–32 (2005)
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. on Computing 17(2), 230–261 (1988)
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. 6845, pp. 483–494. Springer, Heidelberg (2011)
Gabizon, A., Raz, R., Shaltiel, R.: Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J. on Computing 36(4), 1072–1094 (2006)
Goldreich, O., Goldwasser, S., Nussboim, A.: On the implementation of huge random objects. SIAM J. Comput. 39(7), 2761–2822 (2010)
Hennie, F.C.: Crossing sequences and off-line turing machine computations. In: Symposium on Switching Circuit Theory and Logical Design (SWCT) (FOCS), pp. 168–172 (1965)
Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Addison-Wesley Longman Publishing Co., Inc. (1969)
Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: 26th ACM Symp. on the Theory of Computing (STOC), pp. 356–364 (1994)
Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43(2-3), 169–188 (1986)
Kamp, J., Rao, A., Vadhan, S.P., Zuckerman, D.: Deterministic extractors for small-space sources. J. Comput. Syst. Sci. 77(1), 191–220 (2011)
Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)
Li, X.: Improved constructions of three source extractors. In: IEEE Conf. on Computational Complexity, CCC (2011)
Lovett, S., Viola, E.: Bounded-depth circuits cannot sample good codes. Computational Complexity 21(2), 245–266 (2012)
Rao, A.: Extractors for low-weight affine sources. In: IEEE Conf. on Computational Complexity (CCC), pp. 95–101 (2009)
Raz, R.: Extractors with weak random seeds. In: ACM Symp. on the Theory of Computing (STOC), pp. 11–20 (2005)
Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. J. of Computer and System Sciences 33(1), 75–87 (1986)
Shaltiel, R.: How to get more mileage from randomness extractors. Random Struct. Algorithms 33(2), 157–186 (2008)
Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: IEEE Symp. on Foundations of Computer Science (FOCS), pp. 32–42 (2000)
Viola, E.: Extractors for circuit sources. In: IEEE Symp. on Foundations of Computer Science, FOCS (2011)
Viola, E.: The complexity of distributions. SIAM J. on Computing 41(1), 191–218 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Viola, E. (2012). Extractors for Turing-Machine Sources. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2012 2012. Lecture Notes in Computer Science, vol 7408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32512-0_56
Download citation
DOI: https://doi.org/10.1007/978-3-642-32512-0_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32511-3
Online ISBN: 978-3-642-32512-0
eBook Packages: Computer ScienceComputer Science (R0)