Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Dispersers for Affine Sources with Sub-Polynomial Entropy
event speaker icon
Ronen Shaltiel (Haifa University)
event date icon
Wednesday, 13.07.2011, 10:30
event location icon
Room 337-8 Taub Bld.
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.