### Abstract

In his influential 1947 paper that inaugurated the probabilistic method, Erdos proved the existence of 2 log n-Ramsey graphs on n vertices. Matching Erdos' result with a constructive proof is considered a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in the celebrated paper by Barak, Rao, Shaltiel, and Wigderson who constructed a 2^{2(log log n)1-α}-Ramsey graph, for some small universal constant α > 0. In this work, we significantly improve this result and construct 2^{(log logn)c}-Ramsey graphs, for some universal constant c. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two n-bit sources with entropy polylog(n). In fact, our disperser is a zero-error disperser that outputs a constant fraction of the entropy. Prior to this work, such dispersers could only support entropy Ω(n).

Original language | English (US) |
---|---|

Title of host publication | STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Yishay Mansour, Daniel Wichs |

Publisher | Association for Computing Machinery |

Pages | 278-284 |

Number of pages | 7 |

ISBN (Electronic) | 9781450341325 |

DOIs | |

State | Published - Jun 19 2016 |

Event | 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States Duration: Jun 19 2016 → Jun 21 2016 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 19-21-June-2016 |

ISSN (Print) | 0737-8017 |

### Other

Other | 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 |
---|---|

Country | United States |

City | Cambridge |

Period | 6/19/16 → 6/21/16 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Explicit constructions
- Ramsey graphs
- Zero-error dispersers

## Fingerprint Dive into the research topics of 'Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs'. Together they form a unique fingerprint.

## Cite this

*STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 278-284). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897530