In this work, we characterize online linear extractors. In other words, given a matrix $A in mathbb{F}_2^{n times n}$, we study the convergence of the iterated process $mathbf{S} leftarrow Amathbf{S} oplus mathbf{X} $, where $mathbf{X} sim D$ is repeatedly sampled independently from some fixed (but unknown) distribution $D$ with (min)-entropy at least $k$. Here, we think of $mathbf{S} in {0,1}^n$ as the state of an online extractor, and $mathbf{X} in {0,1}^n$ as its input.

As our main result, we show that the state $mathbf{S}$ converges to the uniform distribution for all input distributions $D$ with entropy $k > 0$ if and only if the matrix $A$ has no non-trivial invariant subspace (i.e., a non-zero subspace $V subsetneq mathbb{F}_2^n$ such that $AV subseteq V$). In other words, a matrix $A$ yields an online linear extractor if and only if $A$ has no non-trivial invariant subspace. For example, the linear transformation corresponding to multiplication by a generator of the field $mathbb{F}_{2^n}$ yields a good online linear extractor. Furthermore, for any such matrix convergence takes at most $widetilde{O}(n^2(k+1)/k^2)$ steps.

We also study the more general notion of condensing—that is, we ask when this process converges to a distribution with entropy at least $ell$, when the input distribution has entropy greater than $k$. (Extractors corresponding to the special case when $ell = n$.) We show that a matrix gives a good condenser if there are relatively few vectors $mathbf{w} in mathbb{F}_2^n$ such that $mathbf{w}, A^Tmathbf{w}, ldots, (A^T)^{n-k-1} mathbf{w}$ are linearly dependent. As an application, we show that the very simple cyclic rotation transformation $A(x_1,ldots, x_n) = (x_n,x_1,ldots, x_{n-1})$ condenses to $ell = n-1$ bits for any $k > 1$ if $n$ is a prime satisfying a certain simple number-theoretic condition.

Our proofs are Fourier-analytic and rely on a novel lemma, which gives a tight bound on the product of certain Fourier coefficients of any entropic distribution.

By admin