Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with invariance theorem:
TR14-153 | 14th November 2014
Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Communication with Imperfectly Shared Randomness

Revisions: 2

The communication complexity of many fundamental problems reduces greatly
when the communicating parties share randomness that is independent of the
inputs to the communication task. Natural communication processes (say between
humans) however often involve large amounts of shared correlations among the
communicating players, but rarely allow for perfect sharing of ... more >>>

ISSN 1433-8092 | Imprint