ECCC-Report TR05-067https://eccc.weizmann.ac.il/report/2005/067Comments and Revisions published for TR05-067en-usTue, 05 Jul 2005 13:29:17 +0300
Paper TR05-067
| An Improved Analysis of Mergers |
Zeev Dvir,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2005/067Mergers 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 present a new analysis of the merger construction of [LRVW03]. Our analysis shows that the min-entropy rate of this merger's output is actually $0.52*\delta$ instead of $0.5*\delta$, where $\delta$ is the min-entropy rate of one of the inputs. To obtain this result we deviate from the usual linear algebra methods that were used by [LRVW03] and introduce a new technique that involves results from additive number theory.
Tue, 05 Jul 2005 13:29:17 +0300https://eccc.weizmann.ac.il/report/2005/067