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

Original language | English (US) |
---|---|

Pages (from-to) | 334-345 |

Number of pages | 12 |

Journal | Random Structures and Algorithms |

Volume | 32 |

Issue number | 3 |

DOIs | |

State | Published - May 2008 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

### Keywords

- Derandomization
- Extractors
- Mergers

## Fingerprint Dive into the research topics of 'Analyzing linear mergers'. Together they form a unique fingerprint.

## Cite this

*Random Structures and Algorithms*,

*32*(3), 334-345. https://doi.org/10.1002/rsa.20193