MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.

The adversary doesn't know $y$.

Can person A use a (strong) randomness extractor on the source $W$, where the extractor requires the min-entropy to be $k$?

For person A the output would not be close to uniform since the min-entropy given $y$ is actually $k/3$. However, for the adversary the min-entropy of $W$ is $k$. So is my reasoning correct that for the adversary the output is still close to uniform (i.e. $\epsilon$-close)?

share|cite|improve this question
Maybe I’m missing something, but why should $y$ have anything to do with properties of the output if you apply an extractor just on $W$? – Emil Jeřábek Apr 28 '11 at 16:30
I believe the answer to 'Omega's question is yes. To answer 'none's question below, a "source" is just another term for a random variable. – Ryan O'Donnell May 27 '11 at 23:51
Even if conditioned on y, the entropy of W is zero, the output would continue to look uniform to an adversary who does not know what y is. – Anindya De Dec 10 '11 at 17:24
none ( says in an answer (now moved to this comment): I can't make much sense of this question. I thought min-entropy was something that applies to a (discrete) probability distribution, not a "source". So W|y is just a different distribution. Can you make the question more precise? – Anton Geraschenko Mar 2 '12 at 16:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.