TR05-025 Authors: Zeev Dvir, Ran Raz

Publication: 22nd February 2005 12:30

Downloads: 1345

Keywords:

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.