# No Deterministic Extraction from Santha-Vazirani Sources – A Simple Proof

In my last post I promised a simple proof that there are no deterministic extractors for SV sources. The proof is due to Salil Vadhan, Avi Wigderson and myself and its technique has been used to obtain impossibility results on doing cryptography with SV sources. We show that even more restricted classes of sources are not amenable to deterministic extraction:

Definition For $\delta\in [0,1]$, a source $X$ of length $n$ is $\delta$-imbalanced if for every $x,y\in \{0,1\}^n$, $\Pr[X=x]/\Pr[X=y] \leq (1+\delta)/(1-\delta)$.

A source $X=X_1,X_2,\ldots X_n$ which is $\delta$-imbalanced is an SV source with bias $\delta$ in a very strong sense: every bit $X_i$ has bias at most $\delta$ not only conditioned on the first $i-1$ bits $X_1,X_2,\ldots X_{i-1}$ but also conditioned on all $n-1$ other bits $X_1,X_2,\ldots X_{i-1},X_{i+1},\ldots X_n$. The following lemma shows that there are no deterministic extractors for imbalanced sources and therefore also for SV-sources.

Lemma For every function $f: \{0,1\}^n\rightarrow \{0,1\}$ and every $\delta\in [0,1]$, there is a $\delta$-imbalanced source $X$ such that $f(X)$ has bias at least $\delta$.

Proof There exists a set $S\subset \{0,1\}^n$ of size exactly $2^n/2$ such that $f$ is constant on $S$, say taking value $\sigma\in\{0,1\}$. Consider the source $X$ that with probability $(1+\delta)/2$ outputs a uniformly selected element of $S$ and with probability $(1-\delta)/2$ outputs a uniformly selected element of $\{0,1\}^n\setminus S$. By construction, $f(X)=\sigma$ with probability at least $(1+\delta)/2$, so it has bias at least $\delta$. Moreover, $X$ assigns every  string in $\{0,1\}^n$ probability mass either $((1+\delta)/2)\cdot (1/|S|)=(1+\delta)/2^n$ or $((1-\delta)/2))\cdot (1/|\{0,1\}^n\setminus S|) = (1-\delta)/2^n$.  Thus $X$ is $\delta$-imbalanced.

## One thought on “No Deterministic Extraction from Santha-Vazirani Sources – A Simple Proof”

1. Adam Smith says:

Nice! Despite having taught this proof in a class (!), I was not aware of its origin.