Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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 $\Disp:\F_2^n \ar \B$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $\Disp(V)=\set{0,1}$. This improves the best previous construction of \cite{BK} that achieved $k = \Omega(n^{4/5})$. Our technique follows a high level approach that was developed in \cite{BKSSW,BRSW} in the context of dispersers for two independent general sources. The main steps are: \begin{itemize} \item Adjust the high level approach to make it suitable for affine sources. \item Implement a ``challenge-response game'' for affine sources (in the spirit of \cite{BKSSW,BRSW} that introduced such games for two independent general sources). \item In order to implement the game, we construct extractors for affine block-wise sources. For this we use ideas and components from \cite{Rao09}. \item Combining the three items above, we obtain dispersers for affine sources with entropy that larger than $\sqrt{n}$, and we use a recursive win-win analysis in the spirit of \cite{RSW} to get affine dispersers with entropy less than $\sqrt{n}$. \end{itemize} 53.

Questions and Answers

You need to be logged in to be able to post here.