The Round Complexity of Two-Party Random Selection

Saurabh Sanghvi and Salil Vadhan


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 2n-round protocol that follows from the work 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 set T of density mu with probability at most O(mu+delta)^{1/2}, 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 set T.


  • In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC `05), Baltimore, MD, May 2005.  ACM. 
    [ACM page][Saurabh’s powerpoint slides]
  • Electronic Colloquium on Computational Complexity, TR05-110, October 2005.
    [ECCC page][ps][pdf]
  • SIAM Journal of Computing 38(2):523--550, 2008.  Special Issue on STOC `05. [ps][pdf][SICOMP page]

 [ back to Salil Vadhan's research]