BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/670
DTSTAMP:20230914T125933Z
SUMMARY:Streaming Algorithms for Embedding and Computing Edit Distance in  
 the Low Distance Regime
DESCRIPTION:Speaker: Michal Koucky (Charles University\nDepartment of Compu
 ter Science\nMalosranske nam. 25\, 118 00 Praha 1\nCzech Republic)\n\nAbst
 ract: \nAbstract: The Hamming and the edit metrics are two common notions 
 of measuring distances between pairs of strings $x\,y$ lying in the Boolea
 n hypercube. The edit distance between $x$ and $y$ is defined as the minim
 um number of character insertion\, deletion\, and bit flips needed for con
 verting $x$ into $y$. Whereas\, the Hamming distance between $x$ and $y$ i
 s the number of bit flips needed for converting $x$ to $y$.\n\nIn this tal
 k I will present a randomized injective embedding of the editdistance into
  the Hamming distance with a small (qudratic) distortion. Namely\, for any
  satisfying that their edit distance equals \, the Hamming distance betwee
 n the embedding of and is with high probability. This improves over the di
 stortion ratio of $O(\\log n \\log^* n)$ obtained by Jowhari (2012) for sm
 all values of . Moreover\, the embedding output size is linear in the inpu
 t size and the embedding can be computed using a single pass over the inpu
 t.\n\nI will mention several applications for this embedding. Among our re
 sults we provide a one-pass (streaming) algorithm for edit distance runnin
 g in space and computing edit distance exactly up-to distance. This algori
 thm is based on kernelization for edit distance that is of independent (jo
 int work with Diptarka Chakraborty and Elazar Goldenberg).\n \n
URL:https://www.tcs.tifr.res.in/web/events/670
DTSTART;TZID=Asia/Kolkata:20160406T160000
DTEND;TZID=Asia/Kolkata:20160406T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR