An $(n,k)$-affine source over a finite field $F$ is a random
variable $X=(X_1,...,X_n) \in F^n$, which is uniformly
distributed over an (unknown) $k$-dimensional affine subspace of $
F^n$. We show how to (deterministically) extract practically all
the randomness from affine sources, for any field of size larger
than $n^c$ (where ...
more >>>
In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>
We consider the problem of bit extraction from independent sources. We
construct an extractor that can extract from a constant number of
independent sources of length $n$, each of which have min-entropy
$n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our
constructions are different from recent extractor constructions
more >>>