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-061 | 15th June 2005 00:00

On the Error Parameter of Dispersers

RSS-Feed




TR05-061
Authors: Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
Publication: 15th June 2005 21:46
Downloads: 3207
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint