BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1216
DTSTAMP:20230914T125955Z
SUMMARY:One-way communication and non-adaptive decision trees
DESCRIPTION:Speaker: Swagato Sanyal (IIT Kharagpur)\n\nAbstract: \nFor two 
 Boolean functions f and g acting on n and m bits respectively\, their comp
 osition f o g is a Boolean function on nm bits defined as follows. Its inp
 ut is thought of as consisting of n blocks\, each m bits long. f o g is co
 mputed first by computing g on each block\, and then by computing f on the
  n resulting bits.\nThis talk is about one-way communication complexity of
  composed functions. Here\, there are two communicating parties\, and the 
 input bits are distributed between them. One party sends a message to the 
 other\, based on which the other party outputs their guess of the value of
  the function on the jointly held input.\nSuppose there is an algorithm fo
 r f that queries few bits of f\, possibly randomly\, and outputs the value
  of f. Suppose further that g is a function on very few bits. Then\, the t
 wo communicating parties can simulate this algorithm and compute the compo
 sed function by communicating about as many bits as the algorithm queries.
 \nThe question we ask is if there is a communication protocol that is sign
 ificantly cheaper than this naive protocol. We address this question for t
 wo choices of g: the AND function and the Inner-Product function.\nThis ta
 lk is based on joint work with Nikhil Mande and Suhail Sherif.\n\nLink to 
 the pre-print: https://arxiv.org/pdf/2105.01963.pdf\n
URL:https://www.tcs.tifr.res.in/web/events/1216
DTSTART;TZID=Asia/Kolkata:20220712T153000
DTEND;TZID=Asia/Kolkata:20220712T163000
LOCATION:A201
END:VEVENT
END:VCALENDAR