Theory Lunch Seminar

Tuesday, July 28, 2015 - 12:30pm to 1:30pm

Location:

8102 Gates & Hillman Centers

Speaker:

MADHU SUDAN, Principal Scientist http://research.microsoft.com/en-us/um/people/madhu/

For More Information, Contact:

venkatg@cs.cmu.edu

I will talk about a sequence of works where we investigate basic questions in communication where unreliability can be attributed, not to the channel of communication, but to the lack of perfect synchronization between the communicating players. Topics that will be covered include (some subset of): 1) (One-shot) Compression where sender and receiver of information do not agree on the distribution from which the message is sampled. Can we compress information down to the entropy? 2) Communication complexity when Alice and Bob don't have perfectly shared randomness: Is having shared correlation as good as having perfectly shared randomness? 3) Communication complexity when Alice and Bob don't agree on the function being computed. Can one salvage low-communication protocols with such uncertainty? In most case we have only partial results, and I will describe what we know and the many open questions. Based on joint works with Clement Canonne, Badih Ghazi, Oded Goldreich, Venkatesan Guruswami, Elad Haramaty, Brendan Juba, Adam Kalai, Pritish Kamath, Sanjeev Khanna, Ilan Komargodski, Pravesh Kothari, Jacob Leshno, and Raghu Meka. About the Speaker

Keywords:

Seminar Series