Deterministic extractors for small-space sources. (English) Zbl 1232.68094
Summary: We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space \(s\) sources on \(\{ 0,1\}^n\) as sources generated by width \(2^s\) branching programs. Specifically, there is a constant \(\eta >0\) such that for any \(\zeta >n ^{- \eta }\), our algorithm extracts \(m=(\delta - \zeta )n\) bits that are exponentially close to uniform (in variation distance) from space \(s\) sources with min-entropy \(\delta n\), where \(s=\varOmega (\zeta ^{3}n)\). Previously, nothing was known for \(\delta \leqslant 1/2\), even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of \(r\) independent smaller sources over \(\{ 0,1\}^{\ell }\), where the total min-entropy over all the smaller sources is \(k\). We give deterministic extractors for such sources when \(k\) is as small as polylog(\(r\)), for small enough \(\ell \).
MSC:
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
| 68W20 | Randomized algorithms |
Keywords:
randomness extractors; pseudorandomness; Markov chains; samplable sources; bit-fixing sources; independent sourcesReferences:
| [1] | Alon, N.; Spencer, J. H., The Probabilistic Method, Wiley-Interscience Series (2000), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0996.05001 |
| [2] | Bennett, Charles H.; Brassard, Gilles; Jean-Marc, Robert, Privacy amplification by public discussion, SIAM J. Comput., 17, 2, 210-229 (April 1988) · Zbl 0644.94010 |
| [3] | Bourgain, J.; Glibichuk, A.; Konyagin, S., Estimates for the number of sums and products and for exponential sums in fields of prime order, J. Lond. Math. Soc., 73, 2, 380-398 (2006) · Zbl 1093.11057 |
| [4] | Barak, B.; Impagliazzo, R.; Wigderson, A., Extracting randomness using few independent sources, SIAM J. Comput., 36, 1095-1118 (2006) · Zbl 1127.68030 |
| [5] | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 1-10.; Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 1-10. · Zbl 1192.68468 |
| [6] | Blum, M., Independent unbiased coin flips from a correlated biased source: A finite Markov chain, Combinatorica, 6, 2, 97-108 (1986) · Zbl 0618.60063 |
| [7] | Ben-Or, M.; Linial, N., Collective coin flipping, (Micali, S., Randomness and Computation (1990), Academic Press: Academic Press New York), 91-115 · Zbl 0675.90107 |
| [8] | Bourgain, J., More on the sum-product phenomenon in prime fields and its applications, Int. J. Number Theory, 1, 1-32 (2005) · Zbl 1173.11310 |
| [9] | M. Bellare, J. Rompel, Randomness-efficient oblivious sampling, in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 276-287.; M. Bellare, J. Rompel, Randomness-efficient oblivious sampling, in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 276-287. |
| [10] | Canetti, Ran; Dodis, Yevgeniy; Halevi, Shai; Kushilevitz, Eyal; Sahai, Amit, Exposure-resilient functions and all-or-nothing transforms, (Preneel, Bart, Advances in Cryptology — EUROCRYPT 2000. Advances in Cryptology — EUROCRYPT 2000, Lecture Notes in Comput. Sci., vol. 1807 (May 2000), Springer-Verlag), 453-469 · Zbl 1082.94508 |
| [11] | B. Chor, J. Friedman, O. Goldreich, J. Håstad, S. Rudich, R. Smolensky, The bit extraction problem or \(t\); B. Chor, J. Friedman, O. Goldreich, J. Håstad, S. Rudich, R. Smolensky, The bit extraction problem or \(t\) |
| [12] | Chor, B.; Goldreich, O., Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM J. Comput., 17, 2, 230-261 (1988) · Zbl 0644.94008 |
| [13] | Carter, J. L.; Wegman, M. N., Universal classes of hash functions, J. Comput. System Sci., 18, 143-154 (1979) · Zbl 0412.68090 |
| [14] | A. Cohen, A. Wigderson, Dispersers, deterministic amplification, and weak random sources, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 14-19.; A. Cohen, A. Wigderson, Dispersers, deterministic amplification, and weak random sources, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 14-19. |
| [15] | Yevgeniy Dodis, Exposure-resilient cryptography, PhD thesis, MIT, 2000.; Yevgeniy Dodis, Exposure-resilient cryptography, PhD thesis, MIT, 2000. |
| [16] | Yevgeniy Dodis, Impossibility of black-box reduction from non-adaptively to adaptively secure coin-flipping, Technical Report 039, Electronic Colloquium on Computational Complexity, 2000.; Yevgeniy Dodis, Impossibility of black-box reduction from non-adaptively to adaptively secure coin-flipping, Technical Report 039, Electronic Colloquium on Computational Complexity, 2000. |
| [17] | Dvir, Z.; Raz, R., Analyzing linear mergers, Random Structures Algorithms, 32, 334-345 (2008) · Zbl 1136.68623 |
| [18] | Gabizon, A.; Raz, R.; Shaltiel, R., Deterministic extractors for bit-fixing sources by obtaining an independent seed, SIAM J. Comput., 36, 1072-1094 (2006) · Zbl 1118.68096 |
| [19] | Jun, B.; Kocher, P., The Intel random number generator (1999) |
| [20] | Robert Koenig, Ueli Maurer, Extracting randomness from generalized symbol-fixing and Markov sources, in: Proceedings of 2004 IEEE International Symposium on Information Theory, June 2004, p. 232.; Robert Koenig, Ueli Maurer, Extracting randomness from generalized symbol-fixing and Markov sources, in: Proceedings of 2004 IEEE International Symposium on Information Theory, June 2004, p. 232. |
| [21] | Koenig, Robert; Maurer, Ueli, Generalized strong extractors and deterministic privacy amplification, (Smart, Nigel, Cryptography and Coding 2005. Cryptography and Coding 2005, Lecture Notes in Comput. Sci., vol. 3796 (December 2005), Springer-Verlag), 322-339 · Zbl 1122.94039 |
| [22] | Kamp, J.; Zuckerman, D., Deterministic extractors for bit-fixing sources and exposure-resilient cryptography, SIAM J. Comput., 36, 1231-1247 (2006) · Zbl 1124.68036 |
| [23] | Lichtenstein, D.; Linial, N.; Saks, M., Some extremal problems arising from discrete control processes, Combinatorica, 9, 3, 269-287 (1989) · Zbl 0699.90110 |
| [24] | Lovász, L., Random walks on graphs: A survey, (Miklós, D.; Sós, V. T.; Szőnyi, T., Combinatorics. Combinatorics, Paul Erdős is Eighty, vol. 2 (1996), J. Bolyai Math. Soc.: J. Bolyai Math. Soc. Budapest), 353-398 · Zbl 0854.60071 |
| [25] | Maurer, Ueli; Wolf, Stefan, Privacy amplification secure against active adversaries, (Kaliski, Burton S., Advances in Cryptology — CRYPTO ’97. Advances in Cryptology — CRYPTO ’97, Lecture Notes in Comput. Sci., vol. 1294 (August 1997), Springer-Verlag), 307-321 · Zbl 0898.94007 |
| [26] | Nisan, N.; Ta-Shma, A., Extracting randomness: A survey and new constructions, J. Comput. System Sci., 58, 148-173 (1999) · Zbl 0943.68190 |
| [27] | Nisan, N.; Zuckerman, D., Randomness is linear in space, J. Comput. System Sci., 52, 1, 43-52 (1996) · Zbl 0846.68041 |
| [28] | A. Rao, Extractors for a constant number of polynomially small min-entropy independent sources, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 497-506.; A. Rao, Extractors for a constant number of polynomially small min-entropy independent sources, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 497-506. · Zbl 1301.68194 |
| [29] | Ran Raz, Extractors with weak random seeds, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 11-20.; Ran Raz, Extractors with weak random seeds, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 11-20. · Zbl 1192.68373 |
| [30] | Raz, R.; Reingold, O.; Vadhan, S., Extracting all the randomness and reducing the error in Trevisan’s extractors, J. Comput. System Sci., 65, 1, 97-128 (2002) · Zbl 1020.68029 |
| [31] | Shaltiel, Ronen, Recent developments in explicit constructions of extractors, Bull. Eur. Assoc. Theor. Comput. Sci., 77, 67-95 (June 2002) · Zbl 1051.68070 |
| [32] | R. Shaltiel, How to get more mileage from randomness extractors, in: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 49-60.; R. Shaltiel, How to get more mileage from randomness extractors, in: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 49-60. |
| [33] | Santha, M.; Vazirani, U. V., Generating quasi-random sequences from semi-random sources, J. Comput. System Sci., 33, 75-87 (1986) · Zbl 0612.94004 |
| [34] | Sántha, Miklós; Vazirani, Umesh V., Generating quasirandom sequences from semirandom sources, Twenty-fifth Annual Symposium on Foundations of Computer Science. Twenty-fifth Annual Symposium on Foundations of Computer Science, Singer Island, Fla., 1984. Twenty-fifth Annual Symposium on Foundations of Computer Science. Twenty-fifth Annual Symposium on Foundations of Computer Science, Singer Island, Fla., 1984, J. Comput. System Sci., 33, 1, 75-87 (1986) · Zbl 0612.94004 |
| [35] | Trevisan, L., Extractors and pseudorandom generators, J. ACM, 860-879 (2001) · Zbl 1127.68403 |
| [36] | A. Ta-Shma, On extracting randomness from weak random sources, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 276-285.; A. Ta-Shma, On extracting randomness from weak random sources, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 276-285. · Zbl 0924.68210 |
| [37] | Luca Trevisan, Salil P. Vadhan, Extracting randomness from samplable distributions, in: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 32-42.; Luca Trevisan, Salil P. Vadhan, Extracting randomness from samplable distributions, in: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 32-42. |
| [38] | Vadhan, S., On constructing locally computable extractors and cryptosystems in the bounded-storage model, J. Cryptology, 17, 1, 43-77 (Winter 2004) · Zbl 1071.94016 |
| [39] | U.V. Vazirani, Randomness, adversaries and computation, PhD thesis, EECS, University of California at Berkeley, 1986.; U.V. Vazirani, Randomness, adversaries and computation, PhD thesis, EECS, University of California at Berkeley, 1986. |
| [40] | Umesh V. Vazirani, Efficiency considerations in using semi-random sources (extended abstract), in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York City, 25-27 May 1987, pp. 160-168.; Umesh V. Vazirani, Efficiency considerations in using semi-random sources (extended abstract), in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York City, 25-27 May 1987, pp. 160-168. |
| [41] | Vazirani, Umesh V., Strong communication complexity or generating quasirandom sequences from two communicating semirandom sources, Combinatorica, 7, 4, 375-392 (1987) · Zbl 0643.94002 |
| [42] | von Neumann, J., Various techniques used in connection with random digits, National Bureau of Standards, Applied Mathematics Series, 12, 36-38 (1951) |
| [43] | U.V. Vazirani, V.V. Vazirani, Random polynomial time is equal to slightly-random polynomial time, in: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 417-428.; U.V. Vazirani, V.V. Vazirani, Random polynomial time is equal to slightly-random polynomial time, in: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 417-428. |
| [44] | Wormald, N. C., The differential equation method for random graph processes and greedy algorithms, (Karonski, M.; Proemel, H. J., Lectures on Approximation and Randomized Algorithms (1999), PWN: PWN Warsaw), 73-155 · Zbl 0943.05073 |
| [45] | Wigderson, A.; Zuckerman, D., Expanders that beat the eigenvalue bound: Explicit construction and applications, Combinatorica, 19, 1, 125-138 (1999) · Zbl 0929.05075 |
| [46] | Zuckerman, D., Simulating BPP using a general weak random source, Algorithmica, 16, 367-391 (1996) · Zbl 0857.68121 |
| [47] | Zuckerman, D., Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput., 3, 103-128 (2007) · Zbl 1213.68322 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
