The Taub Faculty of Computer Science Events and Talks

We construct an explicit disperser for affine sources over $\F_2^n$ with entropy $k=2^{\log^{0.9} n}=n^{o(1)}$. This is a polynomial time computable function $D:\F_2^n \to \set{0,1}$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $D(V)=\set{0,1}$. This improves the best previous construction of Ben-Sasson and Kopparty that achieved $k = \Omega(n^{4/5})$ and is the first pseudorandom object for affine sources with entropy less than $\sqrt{n}$.

Our technique follows a high level approach that was introduced by Barak, Kindler, Shaltiel, Sudakov and Wigderson, and further developed by Barak, Rao, Shaltiel and Wigderson, in the context of dispersers for two independent general sources. We implement a "challenge-response game" for affine sources. This game allows the disperser to locate high entropy blocks in the source (even though the disperser only receives a single sample from the source). In order to implement the game we rely (amongst other things) on ideas of Rao in the context of extractors for low-weight affine sources. We also use a recursive win-win analysis that is similar in spirit to that used by Reingold, Shaltiel and Wigderson in order to handle sources with entropy less than $\sqrt{n}$.

I will not assume any previous knowledge on extractors and dispersers.