On the error parameter of dispersers

Ronen Gradwohl*, Guy Kindler, Orner Reingold, Amnon Ta-Shma

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

Abstract

Optimal dispersere have better dependence on the error than optimal extractors. In this paper we give explicit disperser constructions that beat the best possible extractors in some parameters. Our constructions are not strong, but we show that having such explicit strong constructions implies a solution to the Ramsey graph construction problem.

Original languageEnglish (US)
Pages (from-to)294-305
Number of pages12
JournalLecture Notes in Computer Science
Volume3624
DOIs
StatePublished - 2005
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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the error parameter of dispersers'. Together they form a unique fingerprint.

Cite this