Communication with Imperfectly Shared Randomness

A common feature in most natural communication is that it relies on a large shared context between speaker and listener, where the context is shared vaguely rather than precisely. Knowledge of language, technical terms, socio-political events, history etc. all combine to form this shared context; and it should be obvious that no one can expect any part of this context to be shared perfectly by the two parties. This shared context helps in compressing communication (else I would have to include an English dictionary, a book on grammar etc. to this abstract); but the imperfection of the sharing potentially leads to misunderstanding and ambiguity. The challenge of achieving the benefits provided by the shared context without leading to new errors due to the imperfection leads to a host of new mathematical questions. In this talk we will focus on one specific setting for this tension between shared context and imperfection of sharing, namely in the use of shared randomness in communication complexity. It is widely known that shared randomness between speaker and listener can lead to immense savings in communication complexity for certain communication tasks. What happens when this randomness is not perfectly shared? We model this as saying that sender has access to a sequence of uniform random bits and receiver has access to a noisy version of the same sequence where each bit is flipped independently with some probability p. While most known communication protocols fail when the randomness is imperfectly shared, it turns out that many of the effects of shared randomness can be recovered with a slight loss by more carefully designed protocols. Among other results we will describe a general one which shows that any k-bit one-way communication protocol with perfectly shared randomness can be “simulated” with 2k bits of imperfectly shared randomness, and this is essentially tight. Based on joint work with Clément Canonne (Columbia), Venkatesan Guruswami (CMU), and Raghu Meka ().

Speaker Details

Madhu Sudan is a principal researcher at Microsoft Research New England. He got his bachelor’s degree in 1987 from the Indian Institute of Technology Delhi and his Ph.D. in 1992 from the University of California, Berkeley. Before joining Microsoft Research, Sudan had been with IBM (1992-1997) and the Massachusetts Institute of Technology (1997-2009), where he was an associate director of the Computer Science and Artificial Intelligence Laboratory from 2007 to 2009. His main areas of work are in complexity theory and coding theory. Sudan is best known for his work in the design of probabilistically checkable proofs and for algorithms for list decoding of error-correcting codes. He won the Nevanlinna Prize in 2002 and is a fellow of the ACM, the IEEE, the American Mathematical Society, and the American Academy of Arts and Sciences.

Date:
Speakers:
Madhu Sudan
Affiliation:
Microsoft