Analyzing linear mergers
Zeev Dvir, Ran Raz · Random Structures and Algorithms · 2007
Abstract Mergers are functions that transform k (possibly dependent) random sources (distributions) into a single random source, in a way that ensures that if one of the input sources has min‐entropy rate δ then the output has min‐entropy rate close to δ. 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 [Raz, STOC'05] (based on [Lu, Reingold, Vadhan, and Wigderson, STOC'03 pp. 602–611, 2003]). Our analysis uses min‐entropy instead of Shannon's entropy to derive tighter results than the ones obtained in [Raz STOC'05]. We show that for every constant r and k 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. One advantage of our analysis is that b (the min‐entropy of the “good” source) can be as small as a constant (this constant depends on r and k ), while in the analysis given in [Raz STOC'05], b is required to be linear in n . © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008