BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/890
DTSTAMP:20230914T125942Z
SUMMARY:Edit Distance Codes via Synchronization Strings
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Paulson School of\nEngine
 ering and Applied Sciences\n339 Maxwell Dworkin\n33 Oxford Street\nCambrid
 ge\, MA 02138.)\n\nAbstract: \nI will describe a recent approach to design
 ing codes that correct for "editing" errors - i.e.\, where an adversary is
  allowed to delete some of the symbols in a string being transmitted and i
 nsert new symbols. The classical Hamming model of errors (where adversary
  is allowed to change some symbols) may be viewed a special case where the
  number of insertions equals the number of deletions and insertions and de
 letions happen at the same location.\nIn STOC 2017 Haeupler and Shahrasbi 
 introduced an elegant notion that they call a "synchronization string" tha
 t modularly converts standard error-correcting codes into edit distance co
 des with almost no loss in parameters and just a slight loss in alphabet s
 ize\, while retaining algorithmic tractability of error-correction. A conc
 rete example of such a result (from upcoming work with Haeupler and Shahra
 sbi\, ICALP 2018) we show that for every epsilon\, delta and gamma\, ther
 e exists an alphabet Sigma and integer L and (efficient) coding and decodi
 ng schemes over the alphabet Sigma of rate to 1 - delta - epsilon that all
 ow delta fraction deletions and gamma fraction insertions where the decode
 r outputs a list of at most L codewords that is guaranteed to include the 
 transmitted string. In particular the rate does not depend on gamma and in
 deed gamma can be much larger than 1!\nIn this talk I will describe the no
 tion of synchronization strings and this modular reduction from edit dista
 nce coding to Hamming distance coding.\n
URL:https://www.tcs.tifr.res.in/web/events/890
DTSTART;TZID=Asia/Kolkata:20180711T140000
DTEND;TZID=Asia/Kolkata:20180711T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR