Near-Optimal Strong Dispersers

Computer Science/Discrete Mathematics Seminar I
Topic:Near-Optimal Strong Dispersers
Speaker:Dean Doron
Affiliation:The University of Texas at Austin
Date:Monday, February 4
Time/Room:11:00am - 12:00pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/0204-DeanDoron

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs. 

The construction I will show achieves near-optimal seed-length and near-optimal entropy-loss. Viewed as an error-correcting code, we get a binary code with rate approaching $\varepsilon$ that can be list-decoded from $1-\varepsilon$ fraction of erasures. This is the first construction to break the $\varepsilon^2$ rate barrier, solving a long-standing open problem raised by Guruswami and Indyk.