Abstract
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\lt 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 Barak, Kindler, Shaltiel, Sudakov and Wigderson. 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 Frankl and Wilson. 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 Barak et al. that allows us to locate the min-entropy concentrations in a source of low min-entropy.
-
[Alon98]
N. Alon, "The Shannon capacity of a union," Combinatorica, vol. 18, iss. 3, pp. 301-310, 1998.
@article {Alon98, MRKEY = {1721946},
AUTHOR = {Alon, Noga},
TITLE = {The {S}hannon capacity of a union},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
VOLUME = {18},
YEAR = {1998},
NUMBER = {3},
PAGES = {301--310},
ISSN = {0209-9683},
MRCLASS = {05C35 (94A40)},
MRNUMBER = {1721946},
DOI = {10.1007/PL00009824},
ZBLNUMBER = {0921.05039},
} -
[Barak06] B. Barak, A simple explicit construction of an $n^{\Tilde{O}(\log n)}$-Ramsey graph, 2006.
@misc{Barak06,
author = {Barak, Boaz},
TITLE={A simple explicit construction of an $n^{\Tilde{O}(\log n)}$-{R}amsey graph},
NOTE={Tech. report},
ARXIV={math.CO/0601651},
YEAR={2006},
} -
[BarakIW04]
B. Barak, R. Impagliazzo, and A. Wigderson, "Extracting Randomness Using Few Independent Sources," SIAM J. Comput., vol. 36, pp. 1095-1118, 2006.
@article{BarakIW04,
author = {Boaz Barak and R. Impagliazzo and Avi Wigderson},
NOTE = {preliminary version in {\it FOCS} 2004},
TITLE = {Extracting Randomness Using Few Independent Sources},
JOURNAL={SIAM J. Comput.},
VOLUME={36},
PAGES={1095--1118},
YEAR = {2006},
MRNUMBER = {2272272},
ZBLNUMBER = {1127.68030},
DOI = {10.1137/S0097539705447141},
} -
[BarakKSSW05]
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.
@article{BarakKSSW05,
author = {Barak, Boaz and Kindler, G. and Shaltiel, R. and Sudakov, B. and Wigderson, A.},
TITLE = {Simulating independence: {N}ew constructions of condensers, {R}amsey graphs, dispersers, and extractors},
NOTE={preliminary version in {\it STOC} 2005},
JOURNAL={J. ACM},
PAGES={52pp},
VOLUME={57},
YEAR={2010},
MRNUMBER = {2677118},
ZBLNUMBER = {1192.68468},
DOI = {10.1145/1734213.1734214},
} -
[Bourgain05]
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.
@article {Bourgain05, MRKEY = {2172328},
AUTHOR = {Bourgain, J.},
TITLE = {More on the sum-product phenomenon in prime fields and its applications},
JOURNAL = {Int. J. Number Theory},
FJOURNAL = {International Journal of Number Theory},
VOLUME = {1},
YEAR = {2005},
NUMBER = {1},
PAGES = {1--32},
ISSN = {1793-0421},
MRCLASS = {11B75 (11L05)},
MRNUMBER = {2172328},
MRREVIEWER = {Serge{\u\i} V. Konyagin},
DOI = {10.1142/S1793042105000108},
ZBLNUMBER = {1173.11310},
} -
[BourgainKT03]
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.
@article {BourgainKT03, MRKEY = {2053599},
AUTHOR = {Bourgain, J. and Katz, N. and Tao, T.},
TITLE = {A sum-product estimate in finite fields, and applications},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {14},
YEAR = {2004},
NUMBER = {1},
PAGES = {27--57},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {11B75 (11T30)},
MRNUMBER = {2053599},
MRREVIEWER = {Ben Joseph Green},
DOI = {10.1007/s00039-004-0451-1},
ZBLNUMBER = {1145.11306},
} -
[CapalboRVW02]
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.
@inproceedings {CapalboRVW02, MRKEY = {2121193},
AUTHOR = {Capalbo, Michael and Reingold, Omer and Vadhan, Salil and Wigderson, Avi},
TITLE = {Randomness conductors and constant-degree lossless expanders},
BOOKTITLE = {Proceedings of the {T}hirty-{F}ourth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
PAGES = {659--668},
PUBLISHER = {ACM},
ADDRESS = {New York},
YEAR = {2002},
MRCLASS = {68R10 (68W20)},
MRNUMBER = {2121193},
DOI = {10.1145/509907.510003},
ZBLNUMBER = {1192.68475},
} -
[ChorG88]
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.
@article {ChorG88, MRKEY = {0935339},
AUTHOR = {Chor, Benny and Goldreich, Oded},
TITLE = {Unbiased bits from sources of weak randomness and probabilistic communication complexity},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = {SIAM Journal on Computing},
VOLUME = {17},
YEAR = {1988},
NUMBER = {2},
PAGES = {230--261},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {68Q25},
MRNUMBER = {0935339},
MRREVIEWER = {Claus-Peter Schnorr},
DOI = {10.1109/SFCS.1985.62},
ZBLNUMBER = {0644.94008},
} -
[ChungV06] K. -M. Chung and S. Vadhan, Personal communication.
@misc{ChungV06,
author={Chung, K.-M. and Vadhan, S.},
TITLE={personal communication},
} -
[FranklW81]
P. Frankl and R. M. Wilson, "Intersection theorems with geometric consequences," Combinatorica, vol. 1, iss. 4, pp. 357-368, 1981.
@article {FranklW81, MRKEY = {0647986},
AUTHOR = {Frankl, P. and Wilson, R. M.},
TITLE = {Intersection theorems with geometric consequences},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
VOLUME = {1},
YEAR = {1981},
NUMBER = {4},
PAGES = {357--368},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {05C35 (05A17 05A20 05C15)},
MRNUMBER = {0647986},
MRREVIEWER = {E. C. Milner},
DOI = {10.1007/BF02579457},
ZBLNUMBER = {0498.05048},
} -
[Gopalan06]
P. Gopalan, "Constructing Ramsey graphs from boolean function representations," in Proceedings of the 21st Annual IEEE Conference on Computational Complexity, 2006.
@inproceedings{Gopalan06,
author={Gopalan, P.},
TITLE={Constructing {R}amsey graphs from boolean function representations},
BOOKTITLE={Proceedings of the 21st Annual IEEE Conference on Computational Complexity},
VENUE={CCC'06},
YEAR={2006},
DOI = {10.1109/CCC.2006.14},
} -
[Grolmusz00]
V. Grolmusz, "Low rank co-diagonal matrices and Ramsey graphs," Electron. J. Combin., vol. 7, p. 15, 2000.
@article {Grolmusz00, MRKEY = {1756284},
AUTHOR = {Grolmusz, Vince},
TITLE = {Low rank co-diagonal matrices and {R}amsey graphs},
JOURNAL = {Electron. J. Combin.},
FJOURNAL = {Electronic Journal of Combinatorics},
VOLUME = {7},
YEAR = {2000},
PAGES = {Research Paper 15, 7 pp.},
ISSN = {1077-8926},
MRCLASS = {15A33 (05C50 05C55)},
MRNUMBER = {1756284},
ZBLNUMBER = {0939.05060},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r15},
} -
[Guruswami03]
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.
@inproceedings {Guruswami03, MRKEY = {2121629},
AUTHOR = {Guruswami, Venkatesan},
TITLE = {Better extractors for better codes?},
BOOKTITLE = {Proceedings of the 36th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
PAGES = {436--444},
PUBLISHER = {ACM},
ADDRESS = {New York},
YEAR = {2004},
MRCLASS = {68Q25 (68W20 94B35)},
MRNUMBER = {2121629},
DOI = {10.1145/1007352.1007422},
ZBLNUMBER = {1192.68363},
} -
[LuRVW03]
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.
@inproceedings {LuRVW03, MRKEY = {2120441},
AUTHOR = {Lu, Chi-Jen and Reingold, Omer and Vadhan, Salil and Wigderson, Avi},
TITLE = {Extractors: optimal up to constant factors},
BOOKTITLE = {Proceedings of the {T}hirty-{F}ifth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
PAGES = {602--611},
PUBLISHER = {ACM},
ADDRESS = {New York},
YEAR = {2003},
MRCLASS = {68W20 (65C10 68Q25 94B60)},
MRNUMBER = {2120441},
DOI = {10.1145/780542.780630},
ZBLNUMBER = {1192.68859},
} -
[MiltersonNSW95]
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.
@article {MiltersonNSW95, MRKEY = {1649806},
AUTHOR = {Miltersen, Peter Bro and Nisan, Noam and Safra, Shmuel and Wigderson, Avi},
TITLE = {On data structures and asymmetric communication complexity},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {57},
YEAR = {1998},
NUMBER = {1},
PAGES = {37--49},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q25 (68P05)},
MRNUMBER = {1649806},
MRREVIEWER = {Ricardo Baeza-Yates},
DOI = {10.1006/jcss.1998.1577},
ZBLNUMBER = {0920.68042},
} -
[PudlakR04] 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.
@incollection {PudlakR04, MRKEY = {2131412},
AUTHOR = {Pudl{á}k, Pavel and R{ö}dl, Vojt{ě}ch},
TITLE = {Pseudorandom sets and explicit constructions of {R}amsey graphs},
BOOKTITLE = {Complexity of Computations and Proofs},
SERIES = {Quad. Mat.},
VOLUME = {13},
PAGES = {327--346},
PUBLISHER = {Dept. Math., Seconda Univ. Napoli, Caserta},
YEAR = {2004},
MRCLASS = {05C80 (05D10 68Q17)},
MRNUMBER = {2131412},
MRREVIEWER = {David B. Penman},
ZBLNUMBER = {1074.05088},
} -
[Ramsey28]
F. P. Ramsey, "On a problem of formal logic," Proc. London Math. Soc., vol. S2-30, iss. 1, pp. 264-286, 1930.
@article {Ramsey28, MRKEY = {1576401},
AUTHOR = {Ramsey, F. P.},
TITLE = {On a problem of formal logic},
JOURNAL = {Proc. London Math. Soc.},
FJOURNAL = {Proceedings of the London Mathematical Society},
VOLUME = {S2-30},
NUMBER = {1},
PAGES = {264--286},
YEAR={1930},
ISSN = {0024-6115},
MRCLASS = {Contributed Item},
MRNUMBER = {1576401},
DOI = {10.1112/plms/s2-30.1.264},
JFMNUMBER = {55.0032.04},
} -
[Rao06]
A. Rao, "Extractors for a constant number of polynomially small min-entropy independent sources," SIAM J. Comput., vol. 39, pp. 168-194, 2009.
@article{Rao06, MRKEY = {2277175},
AUTHOR = {Rao, Anup},
TITLE = {Extractors for a constant number of polynomially small min-entropy independent sources},
JOURNAL={SIAM J. Comput.},
VOLUME={39},
PAGES={168--194},
YEAR={2009},
NOTE={preliminary version in {\it STOC} 2006},
DOI = {10.1137/060671218},
} -
[Raz05]
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.
@incollection {Raz05, MRKEY = {2181597},
AUTHOR = {Raz, Ran},
TITLE = {Extractors with weak random seeds},
BOOKTITLE = {S{TOC}'05: {P}roceedings of the 37th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
PAGES = {11--20},
PUBLISHER = {ACM},
ADDRESS = {New York},
YEAR = {2005},
MRCLASS = {68Q25 (68R10 68W20)},
MRNUMBER = {2181597},
DOI = {10.1145/1060590.1060593},
ZBLNUMBER = {1192.68373},
} -
[RazRV02]
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.
@article {RazRV02, MRKEY = {1946290},
AUTHOR = {Raz, Ran and Reingold, Omer and Vadhan, Salil},
TITLE = {Extracting all the randomness and reducing the error in {T}revisan's extractors},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {65},
YEAR = {2002},
NUMBER = {1},
PAGES = {97--128},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68P30 (68R10 68W20 68W40)},
MRNUMBER = {1946290},
DOI = {10.1006/jcss.2002.1824},
ZBLNUMBER = {1020.68029},
} -
[ReingoldSW00]
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.
@incollection {ReingoldSW00, MRKEY = {1931801},
AUTHOR = {Reingold, Omer and Shaltiel, Ronen and Wigderson, Avi},
TITLE = {Extracting randomness via repeated condensing},
BOOKTITLE = {41st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience},
VENUE={{R}edondo {B}each, {CA},
2000},
PAGES = {22--31},
PUBLISHER = {IEEE Comput. Soc. Press},
ADDRESS = {Los Alamitos, CA},
YEAR = {2000},
MRCLASS = {68W20},
MRNUMBER = {1931801},
DOI = {10.1109/SFCS.2000.892008},
} -
[SanthaV86]
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.
@article {SanthaV86, MRKEY = {0864080},
AUTHOR = {S{á}ntha, Mikl{ó}s and Vazirani, Umesh V.},
TITLE = {Generating quasi-random sequences from semi-random sources},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {33},
YEAR = {1986},
NUMBER = {1},
PAGES = {75--87},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q99 (65C10 68Q25 68U20)},
MRNUMBER = {0864080},
DOI = {10.1016/0022-0000(86)90044-9},
ZBLNUMBER = {0612.94004},
} -
[Shaltiel02] R. Shaltiel, "Recent developments in explicit constructions of extractors," Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, iss. 77, pp. 67-95, 2002.
@article {Shaltiel02, MRKEY = {1920329},
AUTHOR = {Shaltiel, Ronen},
TITLE = {Recent developments in explicit constructions of extractors},
JOURNAL = {Bull. Eur. Assoc. Theor. Comput. Sci. EATCS},
FJOURNAL = {Bulletin of the European Association for Theoretical Computer Science. EATCS},
NUMBER = {77},
YEAR = {2002},
PAGES = {67--95},
ISSN = {0252-9742},
MRCLASS = {68Q25 (68W20)},
MRNUMBER = {1920329},
ZBLNUMBER = {1051.68070},
} -
[TaShmaZ04]
A. Ta-Shma and D. Zuckerman, "Extractor codes," IEEE Trans. Inform. Theory, vol. 50, iss. 12, pp. 3015-3025, 2004.
@article {TaShmaZ04, MRKEY = {2103480},
AUTHOR = {Ta-Shma, Amnon and Zuckerman, David},
TITLE = {Extractor codes},
JOURNAL = {IEEE Trans. Inform. Theory},
FJOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory},
VOLUME = {50},
YEAR = {2004},
NUMBER = {12},
PAGES = {3015--3025},
ISSN = {0018-9448},
CODEN = {IETTAW},
MRCLASS = {94B60 (94A40)},
MRNUMBER = {2103480},
DOI = {10.1109/TIT.2004.838377},
} -
[Trevisan00]
L. Trevisan, "Extractors and pseudorandom generators," J. ACM, vol. 48, iss. 4, pp. 860-879, 2001.
@article {Trevisan00, MRKEY = {2144932},
AUTHOR = {Trevisan, Luca},
TITLE = {Extractors and pseudorandom generators},
JOURNAL = {J. ACM},
FJOURNAL = {Journal of the ACM},
VOLUME = {48},
YEAR = {2001},
NUMBER = {4},
PAGES = {860--879},
ISSN = {0004-5411},
MRCLASS = {68P30 (65C10 68W20)},
MRNUMBER = {2144932},
DOI = {10.1145/502090.502099},
ZBLNUMBER = {1127.68403},
} -
[Vazirani85]
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.
@inproceedings{Vazirani85,
author={Vazirani, U.},
TITLE={Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources (extended abstract)},
BOOKTITLE={Proceedings of the 17th Annual ACM Symposium on Theory of Computing},
YEAR={1985},
PAGES={366--378},
DOI = {10.1145/22145.22186},
} -
[WigdersonZ99]
A. Wigderson and D. Zuckerman, "Expanders that beat the eigenvalue bound: explicit construction and applications," Combinatorica, vol. 19, iss. 1, pp. 125-138, 1999.
@article {WigdersonZ99, MRKEY = {1722214},
AUTHOR = {Wigderson, Avi and Zuckerman, David},
TITLE = {Expanders that beat the eigenvalue bound: explicit construction and applications},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
VOLUME = {19},
YEAR = {1999},
NUMBER = {1},
PAGES = {125--138},
ISSN = {0209-9683},
MRCLASS = {05C50},
MRNUMBER = {1722214},
MRREVIEWER = {Cyriel Van Nuffelen},
DOI = {10.1007/s004930050049},
ZBLNUMBER = {0929.05075},
}