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