Login
Talks & Seminars
Title: Communication amid uncertainty
Prof. Madhu Sudan, Harvard University
Date & Time: January 3, 2016 10:30
Venue: AG 66 (Lecture Theater), Tata Institute of Fundamental Research, (TIFR)
Abstract:
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.
Speaker Profile:
Professor Madhu Sudan is from the Computer Science department at Harvard University.Professor Sudan has a large body of highly influential work in many areas of Theoretical Computer Science, including Error Correcting Codes, Probabilistically Checkable Proofs, and Property Testing. He has been the recipient of many awards, notably the Nevanlinna Prize awarded in 2002, and the Infosys Prize awarded in 2014. Professor Sudan has recently been offered the Jubilee Professorship by Indian Academy of Sciences. The distinguishing feature envisaged in this professorship is that students, teachers and researchers from India should draw maximum benefits and inspiration by their close interaction with Jubilee Professor. Professor R. K. Shyamsundar, CSE department, IIT Bombay, has been instrumental in coordinating this visit.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback