Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors

ABSTRACT

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2^-k in X. We say that X is a δ-source if its rate k⁄n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministicextractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems.

1. Bipartite Ramsey f1: (0,1)ⁿ)² →0,1, such that for any two independent δ-sources X1, X2 we have f1(X1,X2) = 0,1 This implies a new explicit construction of 2N-vertex bipartite graphs where no induced N^δ by N^δ subgraph is complete or empty.
2. Multiple source extraction f2: (0,1n)³→0,1 such that for any three independent δ-sources X1,X2,X3 we have that f2(X1,X2,X3) is (o(1)-close to being) an unbiased random bit.
3. Constant seed condenser² f3: ⁿ →(0,1^m)^c, such that for any δ-source X, one of the c output distributions f3(X)i, is a 0.9-source over 0,1^m. Here c is a constant depending only on δ.
4. Subspace Ramsey f4: 0,1ⁿ→0,1 such that for any affine-δ-source³ X we have f4(X)= 0,1.

The constructions are quite involved and use as building blocks other new and known gadgets. But we can point out two important themes which recur in these constructions. One is that gadgets which were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. The second is using the input to (introspectively) find high entropy regions within itself.

REFERENCES

• 1: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
• 2: B. Barak, R. Shaltiel, and E. Tromer. True random number generators secure in a changing environment. In Workshop on Cryptographic Hardware and Embedded Systems (CHES), pages 166--180, 2003. LNCS no. 2779.
• 3: M. Ben-Or and N. Linial. Collective coin flipping,robust voting schemes and minima of Banzhaf values. In Proc. 26th FOCS, pages 408--416, 1985.
• 4: E. Ben-Sasson, S. Hoory, E. Rosenman, and S. Vadhan. Personal communication, 2001.
• 5: M. Blum. Independent unbiased coin ips from a correlated biased source: A finite state Markov chain. In Proc. 25th FOCS, pages 425--433, 1984.
• 6: J. Bourgain. More on the Sum-Product Phenomenon in Prime Fields and its Applications, 2005. Unpublished manuscript.
• 7: J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Arxiv technical report, http://arxiv.org/abs/math.CO/0301343, 2003. To appear in GAFA.
• 8: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 9: B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. In Proc. 26th FOCS, pages 429--442, 1985.
• 10: B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky. The bit extraction problem of t-resilient functions (preliminary version). In Proc. 26th FOCS, pages 396--407, 1985.
• 11: A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In Proc. 30th FOCS, pages 14--19. IEEE, 1989.
• 12: Y. Dodis, A. Elbaz, R. Oliveira, and R. Raz. Improved randomness extraction from two independent sources. In Proc. of 8th RANDOM, 2004.
• 13: Yevgeniy Dodis , Joel Spencer, On the (non)Universality of the One-Time Pad, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.376, November 16-19, 2002
• 14: P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357--368, 1981.
• 15: Ariel Gabizon , Ran Raz , Ronen Shaltiel, Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.394-403, October 17-19, 2004 [doi>10.1109/FOCS.2004.21]
• 16: Jesse Kamp , David Zuckerman, Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.92, October 11-14, 2003
• 17: Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780630]
• 18: James L. McInnes , Benny Pinkas, On the Impossibility of Private Key Cryptography with Weakly Random Keys, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.421-435, August 11-15, 1990
• 19: Elchanan Mossel , Christopher Umans, On the complexity of approximating the VC dimension, Journal of Computer and System Sciences, v.65 n.4, p.660-671, December 2002 [doi>10.1016/S0022-0000(02)00022-3]
• 20: P. Pudlak. On explicit ramsey graphs and estimates on the numbers of sums and products, 2005. Unpublished manuscript.
• 21: P. Pudlak and V. Rodl. Pseudorandom sets and explicit constructions of ramsey graphs, 2004. Submitted for publication.
• 22: Ran Raz, Extractors with weak random seeds, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060593]
• 23: O. Reingold , R. Shaltiel , A. Wigderson, Extracting randomness via repeated condensing, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.22, November 12-14, 2000
• 24: M. Santha and U. V. Vazirani. Generating quasi-random sequences from slightly-random sources. In Proc. 25th FOCS, pages 434--440, 1984.
• 25: R. Shaltiel. Recent developments in extractors. Bulletin of the European Association for Theoretical Computer Science, 2002. Available from http://www.wisodm.weizmann.ac.il/~ronens.
• 26: Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece [doi>10.1145/380752.380790]
• 27: L. Trevisan , S. Vadhan, Extracting randomness from samplable distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.32, November 12-14, 2000
• 28: Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
• 29: J. von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12:36--38, 1951.
• 30: D. Zuckerman. General weak random sources. In Proc. 31st FOCS, pages 534--543. IEEE, 1990.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Keywords:
constructions, dispersers condenser, explicit, extractors, ramsey graphs