Skip to content

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

February 21, 2012

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 Comment leave one →
  1. Adam Smith permalink
    March 2, 2012 6:43 pm

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: