ECCC-Report TR05-025https://eccc.weizmann.ac.il/report/2005/025Comments and Revisions published for TR05-025en-usTue, 22 Feb 2005 12:30:39 +0200
Paper TR05-025
| Analyzing Linear Mergers |
Zeev Dvir,
Ran Raz
https://eccc.weizmann.ac.il/report/2005/025Mergers 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.
Tue, 22 Feb 2005 12:30:39 +0200https://eccc.weizmann.ac.il/report/2005/025