×
Barak, Boaz; Rao, Anup; Shaltiel, Ronen; Wigderson, Avi

2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction. (English) Zbl 1256.05146

Ann. Math. (2) 176, No. 3, 1483-1544 (2012).
Summary: The main result of this paper is an explicit disperser for two independent sources on \(n\) bits, each of min-entropy \(k=2^{\log^{\beta}n}\), where \(\beta < 1\) is some absolute constant. Put differently, setting \(N = 2^n\) and \(K = 2^k\), we construct an explicit \(N \times N\) Boolean matrix for which no \(K \times K\) sub-matrix is monochromatic. Viewed as the adjacency matrix of a bipartite graph, this gives an explicit construction of a bipartite \(K\)-Ramsey graph of \(2N\) vertices.
This improves the previous bound of \(k = o(n)\) of B. Barak et al. [in: STOC’05: Proceedings of the 37th annual ACM symposium on theory of computing, Baltimore, MD, USA. New York, NY: Association for Computing Machinery (ACM), 1–10 (2005; Zbl 1192.68468)]. As a corollary, we get a construction of a \(2^{n^{o(1)}}\) (nonbipartite) Ramsey graph of \(2^n\) vertices, significantly improving the previous bound of \(2^{\tilde{O}(\sqrt{n})}\) due to P. Frankl and R. M. Wilson [Combinatorica 1, 357–368 (1981; Zbl 0498.05048)].
We also give a construction of a new independent sources extractor that can extract from a constant number of sources of polynomially small min-entropy with exponentially small error. This improves independent sources extractor of Rao, which only achieved polynomially small error. Our dispersers combine ideas and constructions from several previous works in the area together with some new ideas.
In particular, we rely on the extractors of Raz and Bourgain as well as an improved version of the extractor of Rao. A key ingredient that allows us to beat the barrier of \(k=\sqrt{n}\) is a new and more complicated variant of the challenge-response mechanism of B. Barak et al. (loc. cit) that allows us to locate the min-entropy concentrations in a source of low min-entropy.

Cited in 4 Reviews
Cited in 14 Documents

MSC:

05C55 Generalized Ramsey theory

Keywords:

dispersers; extractors; Ramsey graphs

Citations:

Zbl 1192.68468; Zbl 0498.05048
PDF BibTeX XML Cite
\textit{B. Barak} et al., Ann. Math. (2) 176, No. 3, 1483--1544 (2012; Zbl 1256.05146)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] N. Alon, ”The Shannon capacity of a union,” Combinatorica, vol. 18, iss. 3, pp. 301-310, 1998. · Zbl 0921.05039
[2] B. Barak, A simple explicit construction of an \(n^{\TildeO(\log n)}\)-Ramsey graph, 2006.
[3] B. Barak, R. Impagliazzo, and A. Wigderson, ”Extracting Randomness Using Few Independent Sources,” SIAM J. Comput., vol. 36, pp. 1095-1118, 2006. · Zbl 1127.68030
[4] B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson, ”Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors,” J. ACM, vol. 57, p. 52, 2010. · Zbl 1192.68468
[5] J. Bourgain, ”More on the sum-product phenomenon in prime fields and its applications,” Int. J. Number Theory, vol. 1, iss. 1, pp. 1-32, 2005. · Zbl 1173.11310
[6] J. Bourgain, N. Katz, and T. Tao, ”A sum-product estimate in finite fields, and applications,” Geom. Funct. Anal., vol. 14, iss. 1, pp. 27-57, 2004. · Zbl 1145.11306
[7] M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, ”Randomness conductors and constant-degree lossless expanders,” in Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, 2002, pp. 659-668. · Zbl 1192.68475
[8] B. Chor and O. Goldreich, ”Unbiased bits from sources of weak randomness and probabilistic communication complexity,” SIAM J. Comput., vol. 17, iss. 2, pp. 230-261, 1988. · Zbl 0644.94008
[9] K. -M. Chung and S. Vadhan, Personal communication.
[10] P. Frankl and R. M. Wilson, ”Intersection theorems with geometric consequences,” Combinatorica, vol. 1, iss. 4, pp. 357-368, 1981. · Zbl 0498.05048
[11] P. Gopalan, ”Constructing Ramsey graphs from boolean function representations,” in Proceedings of the 21st Annual IEEE Conference on Computational Complexity, 2006. · Zbl 1349.05230
[12] V. Grolmusz, ”Low rank co-diagonal matrices and Ramsey graphs,” Electron. J. Combin., vol. 7, p. 15, 2000. · Zbl 0939.05060
[13] V. Guruswami, ”Better extractors for better codes?,” in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, New York, 2004, pp. 436-444. · Zbl 1192.68363
[14] C. Lu, O. Reingold, S. Vadhan, and A. Wigderson, ”Extractors: optimal up to constant factors,” in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York, 2003, pp. 602-611. · Zbl 1192.68859
[15] P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson, ”On data structures and asymmetric communication complexity,” J. Comput. System Sci., vol. 57, iss. 1, pp. 37-49, 1998. · Zbl 0920.68042
[16] P. Pudlák and V. Rödl, ”Pseudorandom sets and explicit constructions of Ramsey graphs,” in Complexity of Computations and Proofs, Dept. Math., Seconda Univ. Napoli, Caserta, 2004, vol. 13, pp. 327-346. · Zbl 1074.05088
[17] F. P. Ramsey, ”On a problem of formal logic,” Proc. London Math. Soc., vol. S2-30, iss. 1, pp. 264-286, 1930. · JFM 55.0032.04
[18] A. Rao, ”Extractors for a constant number of polynomially small min-entropy independent sources,” SIAM J. Comput., vol. 39, pp. 168-194, 2009. · Zbl 1185.68453
[19] R. Raz, ”Extractors with weak random seeds,” in STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, New York: ACM, 2005, pp. 11-20. · Zbl 1192.68373
[20] R. Raz, O. Reingold, and S. Vadhan, ”Extracting all the randomness and reducing the error in Trevisan’s extractors,” J. Comput. System Sci., vol. 65, iss. 1, pp. 97-128, 2002. · Zbl 1020.68029
[21] O. Reingold, R. Shaltiel, and A. Wigderson, ”Extracting randomness via repeated condensing,” in 41st Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Comput. Soc. Press, 2000, pp. 22-31. · Zbl 1100.68030
[22] M. Sántha and U. V. Vazirani, ”Generating quasi-random sequences from semi-random sources,” J. Comput. System Sci., vol. 33, iss. 1, pp. 75-87, 1986. · Zbl 0612.94004
[23] R. Shaltiel, ”Recent developments in explicit constructions of extractors,” Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, iss. 77, pp. 67-95, 2002. · Zbl 1051.68070
[24] A. Ta-Shma and D. Zuckerman, ”Extractor codes,” IEEE Trans. Inform. Theory, vol. 50, iss. 12, pp. 3015-3025, 2004. · Zbl 1298.94148
[25] L. Trevisan, ”Extractors and pseudorandom generators,” J. ACM, vol. 48, iss. 4, pp. 860-879, 2001. · Zbl 1127.68403
[26] U. Vazirani, ”Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources (extended abstract),” in Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 366-378.
[27] A. Wigderson and D. Zuckerman, ”Expanders that beat the eigenvalue bound: explicit construction and applications,” Combinatorica, vol. 19, iss. 1, pp. 125-138, 1999. · Zbl 0929.05075
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.