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