Theory Day Session 5

Madhu Sudan – Communication with Imperfectly Shared Randomness

A common feature in 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 (UCLA).

Speaker Details

I joined Microsoft Research New England in Cambridge, Massachusetts as a Principal Researcher in 2009. Previously, from 1997-2009, I was a faculty member in the Electrical Engineering and Computer Science Department at MIT and a member of their Computer Science and Artificial Intelligence Laboratory (CSAIL). Even earlier, from 1992-1997, I was a research staff member at IBM’s Thomas J. Watson Research Center. My educational degrees were from the Indian Institute of Technology at New Delhi (B.Tech., 1983-1987) and the University of California at Berkeley (Ph.D., 1987-1992).

Date:
Speakers:
Madhu Sudan
Affiliation:
Microsoft
    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Madhu Sudan

      Madhu Sudan