This question is actually an exercise problem from Salil Vadhan's draft survey "Pseudorandomness" marked with a star (*) (see Chapter 6, Problem 6.6). I do not know other references.

We say a random variable $X=(X_1,X_2,\cdots,X_n)\in\{0,1\}^n$ comes from a Santha-Vazirani source if for any $0\leq i< n$ and $x_1,x_2,\cdots,x_i\in \{0,1\}$, it holds that: $$ \delta \leq \Pr[X_{i+1}=0\mid X_1=x_1,X_2=x_2,\cdots,X_i=x_i] \leq 1-\delta $$ where $\delta$ is some positive constant.

It is not hard to show that any fixed deterministic extractor (an extractor without a seed) cannot extract even one bit well from some SV-source (the output may be biased with the probability distribution $(\delta, 1-\delta)$ or worse).

It is also known that a seeded extractor $\mathrm{Ext}: \{0,1\}^n\times \{0,1\}^d\to\{0,1\}^m$ exists for SV-sources such that the output is $\epsilon$-close to the uniform distribution (measured by the statistical difference) with the output length $m=\Omega(\delta n)$ and the seed length $d=O(\log(n/\epsilon))$. Actually we have explicit constructions for extracting a constant fraction of min-entropy from any source. In this question the min-entropy is $\Omega(\delta n)$.

The question is: how to extract $\Omega(\delta n)$ bits from SV-sources with a seed of length $d=d(\delta,\epsilon)$ that is independent of $n$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.