- Two Source Extractors for A...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2023

## Two Source Extractors for Asymptotically Optimal Entropy, and Improved Ramsey Graphs

**Speaker:**
Xin Li
, Johns Hopkins University

**Date:**
Tuesday, October 17, 2023

**Time:**
4:15 PM to 5:15 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
32-G449 KIVA

**Event Type:**

**Room Description:**
32-G449 KIVA

**Host:**
Kuikui Liu, CSAIL MIT

**Contact:**
Kuikui Liu, liukui@csail.mit.edu

**Relevant URL:**

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
seminars@csail.mit.edu, theory-seminars@csail.mit.edu

**Reminder Subject:**
TALK: Two Source Extractors for Asymptotically Optimal Entropy, and Improved Ramsey Graphs

Randomness extractors are functions that extract almost uniform random

bits from weak random sources with severe biases. One of the most

important and well studied types of extractors is the so-called two

source extractor, where the input consists of two independent weak

sources. Assuming each source has n bits, one can show the existence of

two source extractors for entropy k =log n+O(1). Such an extractor also

gives a (bipartite) Ramsey graph with N=2^n vertices (on each side),

such that there is no (bipartite) clique or independent set of size

K=O(log N). Explicit constructions of two source extractors and Ramsey

graphs are long standing open problems, dating back to the year of 1947

when Erd˝os invented the probabilistic method.

However, despite considerable effort and several recent breakthroughs,

previously the best explicit two source extractor only works for entropy

k=o(log n log log n). Correspondingly, the best explicit construction of

Ramsey graphs only guarantees the non-existence of a clique or

independent set of size K=(log N)^{o(log log log N)}.

In this talk I will describe a new construction of explicit two source

extractors for asymptotically optimal entropy of k=O(log n), which gives

explicit Ramsey graphs on N vertices with on clique or independent set

of size K=log^c N for some absolute constant c>1. I will also briefly

talk about some other applications.

Milk & Cookies served at 4pm, talk to begin at 4:15pm.

**Research Areas:**

Algorithms & Theory

**Impact Areas:**

Created by Nathan Higgins at Friday, October 13, 2023 at 2:07 PM.