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:

See other events that are part of the Theory of Computation (ToC) Seminar 2023.

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