slideshow 3

Complexity seminar

Entropy extractors for small zero fixing sources

Pavel Pudlák
IM

 

Friday, 11. January 2019 - 13:30 to 15:00
in IM, rear building, ground floor

A (k,n)-zero fixing source X is given by a subset S of [n] of size k. The source X produces 0-1 vectors that are zero outside of S each with probability 2^{-k}. An extractor for a (k,n)-zero fixing source is a mapping F:{0,1}^n\to {0,1}^l such that F(X) is close to the uniform distribution on {0,1}^l. Such extractors are known for k down to log log n with l=k-O(1). In this talk we will show some constructions for k << log log n and some upper bounds on the amount of entropy that is possible to extract for small k.

These problems are closely connected with Ramsey theory.

Joint work with Vojtěch Rodl.