A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>
We study the problem of constructing affine extractors over \mathsf{GF(2)}. Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which relies heavily on the technique of Van der Corput differencing and a careful choice of a ... more >>>
We give the first explicit construction of deterministic extractors for affine sources over F_2, with entropy k \geq \log^C n for some large enough constant C, where n is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>>
Given a function f:\mathbb F_2^n \to [-1,1], this work seeks to find a large affine subspace \mathcal U such that f, when restricted to \mathcal U, has small nontrivial Fourier coefficients.
We show that for any function f:\mathbb F_2^n \to [-1,1] with Fourier degree d, there exists an affine subspace ... more >>>
We study extractors computable in uniform \mathrm{AC}^0 and uniform \mathrm{NC}^1.
For the \mathrm{AC}^0 setting, we give a construction such that for every k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}, it can extract (1-\gamma)k randomness from an (n, k) source for an arbitrary constant ...
more >>>