BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/721
DTSTAMP:20230914T125935Z
SUMMARY:Interactive Communication Over a Noisy Channel
DESCRIPTION:Speaker: Varsha Dani (University of New Mexico\nDepartment of C
 omputer Science\n2205 Cutler Ave.\nAlbuquerque\, NM 87106\nUnited States o
 f America)\n\nAbstract: \nAlice and Bob want to hold a conversation over a
  noisy channel on which adversarially chosen bits may be flipped. How can 
 they communicate robustly despite such an attack?\n\nWhen the conversation
  is one-way\, i.e. Alice wants to send Bob a single message\, this is a we
 ll studied problem\, solved by error-correcting codes. However\, these cod
 es are not useful\, for instance\, when Alice and Bob need to take turns s
 ending single bits.  To solve this problem\, Schulman (1992) invented tre
 e codes\, showing that for sufficiently small noise rates the conversation
  can be robustly simulated using a constant factor blowup in communication
 . Subsequently there were a number of improvements\, culminating in a rece
 nt result of Haeupler (2014) conjectured to be optimal.\n\nThe drawback in
  the above is that it depends on knowing the noise rate. We approach the p
 roblem from a different angle\, asking what Alice and Bob can do if they h
 ave no estimate for the noise on the channel (indeed\, if they do not even
  know if there *is* any noise). We show that\, with some caveats\, even in
  this setting Alice and Bob can robustly hold their conversation\, with a 
 communication rate comparable to Haeupler's with respect to the actual (a 
 posteriori) noise rate.\n
URL:https://www.tcs.tifr.res.in/web/events/721
DTSTART;TZID=Asia/Kolkata:20161108T160000
DTEND;TZID=Asia/Kolkata:20161108T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR