BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/82
DTSTAMP:20230914T125909Z
SUMMARY:Lower Bounds for Noisy Computations
DESCRIPTION:Speaker: Chinmoy Dutta\nTata Institute of Fundamental Research\
 nSchool of Technology and Computer Science\nHomi Bhabha Road\n\nAbstract: 
 \nWe consider noisy distributed computation in the setting of wireless sen
 sor networks\, where processors are placed randomly on a unit square. They
  communicate with each other by broadcasting messages in order to compute 
 some function whose input is distributed among them. Constraints on power 
 usage limit the range and the number of transmissions. Furthermore\, messa
 ges often get corrupted during transmission.  Recently\, protocols have be
 en proposed to compute efficiently in this model. We show the first lower 
 bounds in this model: in order to compute the PARITY or MAJORITY of N bits
  reliably\, at least N log log N transmission are necessary. This shows th
 at the currently known protocols for these functions are optimal. The tech
 niques developed in this work can also be used to prove lower bounds for n
 oisy decision trees.\n
URL:https://www.tcs.tifr.res.in/web/events/82
DTSTART;VALUE=DATE:20100416
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR