[Mittagsseminar TI] Mittagsseminar am 26. u. 28.05.2015

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

   Dienstag, 26.05.2015
   Karl Bringmann
   zum Thema:
     Quadratic Conditional Lower Bounds for String Problems and Dynamic
     Time Warping

   Abstract:
Longest common subsequence and edit distance are classic similarity
measures of strings. Dynamic time warping is a classic similarity
measure of curves. These measures can be computed by simple quadratic
time dynamic programming algorithms, and despite much effort no
algorithms with significantly better running time are known.
We prove that, even restricted to binary strings or one-dimensional
curves, respectively, these measures do not have strongly subquadratic
time algorithms, i.e., no algorithms with running time O(n^{2−eps}) for
any eps>0, unless the Strong Exponential Time Hypothesis fails. We
generalize the result to edit distance for arbitrary fixed costs of the
four operations (deletion, insertion, matching, substitution), by
identifying trivial cases that can be solved in constant time, and
proving quadratic-time hardness on binary strings for all other cost
choices.


und am

   Donnerstag, 28.05.2015
   Klaus Kriegel
   zum einem noch bekannt zu gebenden Thema

***************************************************
Ort: Takustr. 9, RM 055

Uhrzeit: 12 Uhr s.t.
***************************************************

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature