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.

1 de diciembre de 2015

Poniendo FoQCoSS en los fundamentos de la computación cuántica

Nos acaban de aprobar el proyecto STIC-AmSud "FoQCoSS - Foundations of Quantum Computation: Syntax and Semantics" (Fundamentos de la computación cuántica: sintaxis y semántica).

Este es un proyecto conjunto donde participan 5 instituciones (dos argentinas, una brasileña y cuatro francesas) y un total de 11 investigadores y becarios.
Los miembros argentinos somos los miembros argentinos de este blog, Gabriel Senno y, quien les escribe, Alejandro Díaz-Caro.

El objetivo del proyecto, como lo dice el título, es estudiar los fundamentos de la computación cuántica, con 5 objetivos específicos claros:
  1. Estudiar el fenómeno del paralelismo, utilizando las extensiones algebraicas al lambda cálculo.
  2. Estudiar la semántica denotacional del lambda cálculo vectorial.
  3. Estudiar sistemas modulo isomorfismos de tipos.
  4. Estudiar la  semántica categórica del lambda cálculo cuántico del equipo brasileño en el proyecto.
  5. Estudiar los las consecuencias de la teoría de la computabilidad en la física y las consecuencias de la física en la teoría de la computabilidad.

Es un proyecto a dos años que nos va a permitir reunirnos todos en jornadas de trabajo un par de veces al año y es financiado por MAEDI e INRIA de Francia, CAPES de Brasil y MINCYT de Argentina.

Les dejo el link a la descripción completa del proyecto en la página de STIC-AmSud.

Los integrantes somos (en orden alfabético):
  1. Pablo ARRIGHI – Université Aix-Marseille, Francia
  2. Alejandro DIAZ-CARO – Universidad Nacional de Quilmes, Argentina
  3. Gilles DOWEK – INRIA, Francia
  4. Stefano FACCHINI – Université Aix-Marseille, Francia
  5. Juliana KAIZER VIZZOTTO – Universidade Federal de Santa Maria, Brasil
  6. Simon MARTIEL – INRIA, Francia
  7. Simon PERDRIX – CNRS/LORIA, Francia
  8. José Carlos PUIATI PIRES – Universidade Federal de Santa Maria, Brasil
  9. Gabriel SENNO – Universidad de Buenos Aires, Argentina
  10. Benoît VALIRON – CentraleSupélec –LRI, Francia
  11. Hanry (Quanlong) WANG – LORIA, Francia

28 de noviembre de 2015

Proyectos

Tenemos bastante abandonado el blog. Por mi parte mis excusas son que este semestre he estado dictando varios cursos a la vez (1 en la Tecnicatura en Programación Informática, 2 en la Licenciatura en Informática y 1 en la Maestría en Bioinformática, de la UNQ), ya que el semestre que viene no dictaré clase alguna en Quilmes porque me voy todo el semestre a Turín.

Presentadas las correspondientes excusas, les cuento en qué estoy trabajando actualmente, proyectos y demás. (Ah! Y estoy buscando buenos estudiantes que quieran engancharse en alguno de los temas para hacer su doctorado!).

En primer lugar, con Fidel (Pablo E. Martínez López) terminamos una implementación de λ⁺, la extensión a λ-cálculo que hicimos con Gilles Dowek donde tipos isomorfos son considerados iguales. Ya hablé de este trabajo en un post anterior (no dejen de leerlo). Lo que terminamos de hacer ahora es corregir todo lo que había que corregir de la versión presentada en IFL, y enviado a evaluación al post-proceedings de esa conferencia para su publicación. El lunes subiré el paper, tal como lo enviamos, a mi página web (no tengo acceso a ella desde mi casa). Update: Aquí está.

Por otro lado, con Abuzer Yakaryilmaz enviamos un paper para su revisión. Abuzer es especialista en Autómatas Cuánticos, y juntos diseñamos un autómata que dimos en llamar autómata afín, el cual es una especie de autómata probabilista... sólo que acepta probabilidades negativas. Dicho de otro modo, acepta "probabilidades" en los reales tales que la suma de ellas dé 1. Es como eliminar el axioma de que las probabilidades deben ser positivas. Lo interesante es que con dicho autómata podemos recrear la interferencia destructiva que existe en la cuántica (la cual existe justamente porque las "amplitudes" pueden ser negativas y por lo tanto pueden cancelarse con otras positivas).
También allí les debo el paper ya que aún no lo subí a mi página web. Veré de subirlo esta semana y actualizar el link aquí. Update: El paper fue aceptado. Más info y link de descarga aquí.

Finalmente, una tercera línea, es con Gilles Dowek, con quien nos basamos en las ideas desarrolladas en λ⁺ para definir un cálculo donde la medición cuántica proyectiva se interpreta como una conjunción conmutativa. Ya comenté de este trabajo hace unos meses. El paper ahora está listo (otro más que tengo que subir a mi página). Update: Lo pueden bajar de aquí -> arXiv:1601.04294.

Como adelanté al principio, les cuento que de Enero a Julio estaré en Italia, a donde iré como profesor invitado a la Università di Torino a trabajar con Mariangiola Dezani-Ciancaglini y Simona Ronchi della Rocca. El proyecto es utlizar tipos unión e intersección (de los cuales Mariangiola y Simona son expertas) para caracterizar ciertas propiedades de la computación cuántica. Aunque también trabajaremos en otros temas: con Mariangiola este año comenzamos un trabajo sobre el "preciseness" del subtipado con unión e intersección. Veremos qué surge de todo eso. Son seis meses para interactuar en temas de tipos unión e intersección, más cuántica.

Eso es todo por ahora. Les recuerdo el tema con el que comencé el post: si estás terminando tu Licenciatura en Ciencias de la Computación (o carreras afines) y te interesan estos temas, no dudes en contactarme ya que estoy buscando buenos estudiantes que quieran venir a hacer un doctorado conmigo a Quilmes. También hay posibilidades para tesinas de grado. Mi mail y teléfono lo encuentran en mi página web.