In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, Z)$, where $Z$ is a seed distribution that is independent from both $X$ and $Y$, looks random. This can be equivalently viewed as an "adversary", who has some limited knowledge $Y$ of $X$, cannot predict ${\rm Ext}(X, Z)$.

My question concerns the case where the adversary knows something about $Z$. I model this situation as that there is another random variable $M$ (say of $O(1)$ bits), that is allowed to be correlated with both $X$ and $Z$. Of course, if there is no structure about $M$, then there is no hope. As an example, suppose that $M = {\rm Ext}_1(X, Z)$ where $\rm Ext_1$ is the projection of $\rm Ext$ to its first bit, then clearly one cannot hope that the joint distribution $(M, Y, {\rm Ext}(X, Z))$ looks random.

My question is then the case where we do know something about $M$. Specifically, consider the case that the correlation between any bit of $M$ and any bit of ${\rm Ext}(X, Z)$ is small. In other words, $(M, {\rm Ext}(X, Z))$ is close to $(M, U)$ where $U$ is the uniform distribution (or modeling in another way, $(M, {\rm Ext}(X, Z))$ is close to $(U, {\rm Ext}(X, Z))$.

Do we know extractor constructions in this situation? Any pointer or reference? This problem seems pretty natural.


  • 1
    $\begingroup$ I'm not sure what you are asking. If you assume that $(M,Ext(X,Z))$ is close to $(M,U)$, you are done, correct? If you just assume that the correlation between $M$ and any bit if $Ext(X,Z)$ is small, then you cannot conclude that $Ext(X,Z)$ looks random given $M$ since, for example, $M$ could be the parity of all the bits of $Ext(X,Z)$. Can you clarify the assumption and the property you want from the construction? $\endgroup$
    – Adam Smith
    Jul 31 '15 at 14:03
  • $\begingroup$ Thank you Adam for the comments . Also thanks for the second part. It's my fault that I am not clear about the question at this point and sorry for confusion. Before I think more and edit, just raise a probably naive point: I want to conclude $(M, Y, Ext(X, Z))$ and $(M, Y, U)$ are close, from $(M, Ext(X, Z))$ is close to $(M, U)$. Would that additional Y possibly reveal more information then? $\endgroup$
    – Xi Wu
    Jul 31 '15 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.