Résumé : We will discuss the complexity of one of the most basic problems in pattern matching, that of approximating the Hamming distance. Given a pattern P of length n the task is to output an approximation of the Hamming distance (that is, the number of mismatches) between P and every n-length substring of a longer text. We provide the first efficient one-way randomised communication protocols as well as a new, fast and space efficient streaming algorithm for this problem.
| Dernière modification : Monday 27 May 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |