Near-Optimal Strong Dispersers

Near-Optimal Strong Dispersers - Dean Doron

Dean Doron
The University of Texas at Austin
February 4, 2019

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.