Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ronen Gradwohl:

TR06-026 | 27th February 2006
Ronen Gradwohl, Salil Vadhan, David Zuckerman

Random Selection with an Adversarial Majority

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

TR05-061 | 15th June 2005
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

On the Error Parameter of Dispersers

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 ... more >>>

ISSN 1433-8092 | Imprint