2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction

ABSTRACT

The main result of this paper is an explicit disperser for two independent sources on n bits, each of entropy k=n^o(1). Put differently, setting N=2ⁿ and K=2^k, we construct explicit N x N Boolean matrices for which no K x K submatrix is monochromatic. Viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of K-Ramsey bipartite graphs of size N.This greatly improves the previous bound of k=o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson [4]. It also significantly improves the 25-year record of k = Õ (√n) on the special case of Ramsey graphs, due to Frankl and Wilson [9].The construction uses (besides "classical" extractor ideas) almost all of the machinery developed in the last couple of years for extraction from independent sources, including:

• Bourgain's extractor for 2 independent sources of some entropy rate < 1/2 [5]
• Raz's extractor for 2 independent sources, one of which has any entropy rate > 1/2 [18]
• Rao's extractor for 2 independent block-sources of entropy n^{Ω (1)} [17]
• The "Challenge-Response" mechanism for detecting "entropy concentration" of [4].

The main novelty comes in a bootstrap procedure which allows the Challenge-Response mechanism of [4] to be used with sources of less and less entropy, using recursive calls to itself. Subtleties arise since the success of this mechanism depends on restricting the given sources, and so recursion constantly changes the original sources. These are resolved via a new construct, in between a disperser and an extractor, which behaves like an extractor on sufficiently large subsources of the given ones.This version is only an extended abstract, please see the full version, available on the authors' homepages, for more details.

REFERENCES

• 1: N. Alon. The shannon capacity of a union. Combinatorica, 18, 1998.
• 2: B. Barak. A simple explicit construction of an nTildeo(log n)-ramsey graph. Technical report, Arxiv, 2006. http://arxiv.org/abs/math.CO/0601651.
• 3: 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]
• 4: Boaz Barak , Guy Kindler , Ronen Shaltiel , Benny Sudakov , Avi Wigderson, Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060592]
• 5: J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1--32, 2005.
• 6: J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis, 14:27--57, 2004.
• 7: 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]
• 8: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 9: P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357--368, 1981.
• 10: P. Gopalan. Constructing ramsey graphs from boolean function representations. In Proceedings of the 21th Annual IEEE Conference on Computational Complexity, 2006.
• 11: V. Grolmusz. Low rank co-diagonal matrices and ramsey graphs. Electr. J. Comb, 7, 2000.
• 12: V. Guruswami. Better extractors for better codes? Electronic Colloquium on Computational Complexity (ECCC), (080), 2003.
• 13: 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]
• 14: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 15: Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167162]
• 16: P. Pudlak and V. Rodl. Pseudorandom sets and explicit constructions of ramsey graphs. Submitted for publication, 2004.
• 17: Anup Rao, Extractors for a constant number of polynomially small min-entropy independent sources, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132589]
• 18: 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]
• 19: 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
• 20: Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
• 21: R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, 77:67--95, 2002.
• 22: A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50, 2004.
• 23: U V Vazirani, Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.366-378, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22186]
• 24: A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125--138, 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Ramsey graphs, dispersers, extractors, independent sources