An improved analysis of mergers

Zeev Dvir, Amir Shpilka

Research output: Contribution to journalConference articlepeer-review

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 δ 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 present a new analysis of the merger construction of [6]. Our analysis shows that the min-entropy rate of this merger's output is actually 0.52 · δ instead of 0.5·δ, where δ 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 [6] and introduce a new technique that involves results from additive number theory.

Original languageEnglish (US)
Pages (from-to)270-281
Number of pages12
JournalLECTURE NOTES IN COMPUTER SCIENCE
Volume3624
DOIs
StatePublished - Jan 1 2005
Externally publishedYes
Event8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005 - Berkeley, CA, United States
Duration: Aug 22 2005Aug 24 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An improved analysis of mergers'. Together they form a unique fingerprint.

Cite this