Charla: "The k-mismatch problem revisited"


Compartir
Charlista: 
Allyx Fontaine
Fecha: 
4 Noviembre, 2015 - 14:30
Sala: 
Auditorio DCC 315 (Poniente)
Organización: 
Prof. Jérémy Barbay, académico DCC

 

Resumen:

We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern and every pattern-length substring of a text, as long as that Hamming distance is at most k. Whenever the Hamming distance is greater than k, we simply output "No"'. We give improved algorithms for this problem in both the standard offline setting and also as a streaming model.