Abstract:
Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate $\delta$ then the output has min-entropy rate close to $\delta$. Mergers have proven to be a very useful tool in explicit constructions of extractors and condensers, and are also interesting objects in their own right. In this work we give a refined analysis of the merger constructed by \cite{Raz05} (based on \cite{LRVW03}). Our analysis uses min-entropy instead of Shannon's entropy to derive tighter results than the ones obtained in \cite{Raz05}. We show that for every r it is possible to construct a merger that takes as input k strings of length n bits each, and outputs a string of length n/r bits, such that if one of the input sources has min-entropy b, the output will be close to having min-entropy b/(r+1). This merger uses a constant number of additional uniform bits when k and r are constants. One advantage of our analysis is that b (the min-entropy of the 'good' source ) can be as small as a constant, while in the analysis given in \cite{Raz05}, b is required to be linear in n.