TR05-110 Authors: Saurabh Sanghvi, Salil Vadhan

Publication: 3rd October 2005 12:30

Downloads: 2151

Keywords:

We study the round complexity of two-party protocols for

generating a random $n$-bit string such that the output is

guaranteed to have bounded bias (according to some measure) even

if one of the two parties deviates from the protocol (even using

unlimited computational resources). Specifically, we require that

the output's statistical difference from the uniform distribution

on {0,1}^n is bounded by a constant less than 1.

We present a protocol for the above problem that has 2log*n+O(1)

rounds, improving a previous 2n-round protocol of Goldreich,

Goldwasser, and Linial (FOCS `91). Like the GGL protocol, our

protocol actually provides a stronger guarantee, ensuring that the

output lands in any subset T of {0,1}^n of density mu with

probability at most O(sqrt(mu+delta)), where delta is an

arbitarily small constant.

We then prove a matching lower bound, showing that any protocol

guaranteeing bounded statistical difference requires at least

log*n-log*log*n-O(1) rounds. As far as we know, this is

the first nontrivial lower bound on the round complexity of random

selection protocols (of any type) that does not impose additional

constraints (e.g. on communication or ``simulatability'').

We also prove several results for the case when the output's bias is

measured by the maximum multiplicative factor by which a party

can increase the probability of a subset T in {0,1}^n.