Tel-Aviv University - Computer Science Colloquium
Sunday, January 2, 14:15-15:15
at 14:00
Schreiber Building, Room 309
Noncryptographic Selection
Protocols
Uriel Feige
Weizmann Institute
Abstract:
Selection tasks generalize some well studied problems, such as
collective coin flipping and leader election. We present new selection
protocols in the full information model, and new negative results.
In
particular, when there are $(1 + \delta)n/2$ good players, we show
a
protocol that chooses a good leader with probability
$\Omega(\delta^{1.65})$, and show that every leader election protocol
has success probability $O(\delta^{1 - \epsilon})$, for every $\epsilon
> 0$. Previously known protocols for this problem have success
probability that is exponentially small in $1/\delta$, and no
nontrivial upper bounds on the success probability were known.
For colloquium schedule, see
http://www.math.tau.ac.il/~zwick/colloq.html