Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-067 | 28th June 2005 00:00

An Improved Analysis of Mergers

RSS-Feed




TR05-067
Authors: Zeev Dvir, Amir Shpilka
Publication: 5th July 2005 13:29
Downloads: 3773
Keywords: 


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 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.



ISSN 1433-8092 | Imprint