BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/11
DTSTAMP:20230914T125906Z
SUMMARY:Communication Complexity for Dummies
DESCRIPTION:Speaker: Ajesh Babu\nSchool of Technology and Computer Science\
 nTata Institute of Fundamental Research\nHomi Bhabha Road\n\nAbstract: \nT
 he notion of communication complexity (CC) was introduced by Yao in 1979\,
  who investigated the following problem involving two separated parties (A
 lice and Bob). Alice receives an n-bit string x and Bob another n-bit stri
 ng y\, and the goal is for one of them (say Bob) to\ncompute a certain fun
 ction f(x\,y) with the least amount of communication between them. Note th
 at here we are not concerned about the number of computational steps\, or 
 the size of the computer memory used. Communication complexity tries to qu
 antify the amount of\ncommunication required for such distributed computat
 ions. Of course they can always succeed by having Alice send her whole n-b
 it string to Bob\, who then computes the function\, but the idea here is t
 o find clever ways of calculating f with less than n bits of communication
 . \n\nReference: Communication complexity By Eyal Kushilevitz\, Noam Nisan
 \n(We will try to cover the first chapter of this book.)\n
URL:https://www.tcs.tifr.res.in/web/events/11
DTSTART;VALUE=DATE:20090703
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR