ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-151 | 10th December 2006 00:00

The communication complexity of correlation

RSS-Feed

Abstract:

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated without the knowledge of D. There
are two settings based on how the distribution D provided to
Alice is chosen.



ISSN 1433-8092 | Imprint