4 de enero de 2016

Rūsiņš Mārtiņš Freivalds 1942-2016

Hoy me llegó la triste noticia de que Rūsiņš Freivalds falleció. El fue un pionero de la teoría de autómatas y la complejidad computacional. Entre sus muchas contribuciones quisiera resaltar  el primer algoritmo que demuestra la superioridad de la computación probabilística sobre la determinística; el demostró que el lenguaje {0n1n | n≥0} puede ser reconocido por un autómata probabilístico. También, fue el descubridor de un algoritmo asintóticamente óptimo para verificar la multiplicación de matrices, conocido como el Algoritmo de Freivalds

Tuve el placer de conocerlo y escuchar en varias ocasiones sus historias sobre como hacían investigación en la antigua unión soviética, del cual Latvia (o Letonia en español) fue parte. Siempre que él iba a alguna conferencia estaba acompañado de sus muchos estudiantes. En los últimos años sus trabajos se centraron en un modelo de computación basado en números p-ádicos. Aunque aparenta ser un modelo muy extraño, es una generalización muy natural y muy interesante.