BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/539
DTSTAMP:20230914T125928Z
SUMMARY:Coding for Interactive Communication: A survey on recent progress
DESCRIPTION:Speaker: Madhu Sudan (Microsoft Research\, New England)\n\nAbst
 ract: \nIn a seminal work in 1992\, Schulman raised the question of whethe
 r an interaction can be protected from errors that occur on a noisy channe
 l. He also gave some surprisingly positive answers showing that a constant
  fraction of adversarial errors can be corrected while incurring only a co
 nstant factor blowup in the number of bits exchanged. Recently this line o
 f research was revived by the works of Braverman and Rao (2009)\, who gave
  essentially optimal results on the fraction of errors that could be corre
 cted. Both the above papers rely on a combinatorial structure called a tre
 e code for which efficient construction and decoding algorithms are not kn
 own - as a result all the previous papers led to algorithmically inefficie
 nt results. This was remedied to some extent by Brakerski and Kalai who in
 jected a new idea that also suggested ways of achieving many of the result
 s algorithmically with use only of small tree codes. Very recently Haeuple
 r and Ghaffari building on works by Braverman and Efremenko and the above 
 mentioned papers gave algorithmically efficient results matching all the k
 nown information-theoretic limits. Along the way Haeupler also gives a sol
 ution to the Interactive Communication problem without any tree codes. In 
 this talk I will survey some of the main ideas behind the results (to the 
 best of my understanding).\n
URL:https://www.tcs.tifr.res.in/web/events/539
DTSTART;TZID=Asia/Kolkata:20141004T113000
DTEND;TZID=Asia/Kolkata:20141004T130000
LOCATION:AG-66
END:VEVENT
END:VCALENDAR