Continuando con autómatas afines

En una entrada anterior Alejandro había anunciado un nuevo paper sobre una idea de un modelo de computación con transformaciones afines. A modo de continuación de ese artículo, este servidor en coautoría con Abuzer Yakaryilmaz, acabamos de hacer público una continuación a la idea de lo autómatas afines. Se puede descargar el manuscrito directamente desde arXiv. En este caso nos concentramos en la complejidad descripcional de dichos computadores con varios resultados interesantes.

También aprovecho esta ocasión para resaltar otra continuación más de este mismo paper, titulado "Can one quantum bit separate any pair of words with zero-error?," escrito por Belovs, Montoya y Yakaryilmaz; también puede descargarse desde arXiv. En este artículo en particular se mira un problema muy sencillo de explicar pero bastante complejo de resolver, el de separar palabras. Por ejemplo, si te doy x e y, ¿cuál él es el autómata de tamaño mínimo que acepta x y rechaza y?

Entonces, por lo que va de año ya son 3 los artículos sobre autómatas afines. ¿Será el inicio de una línea de invetigación? Solo el tiempo lo dirá. Por ahora, el modelo es muy interesante y prometedor ya que simplifica muchos argumentos en la teoría de autómatas cuánticos.

Computación afín y autómatas afines, en Rusia

El paper que escribimos con Abuzer Yakaryılmaz (el cual comenté aquí), fue aceptado en el CSR 2016 (The 11th International Computer Science Symposium in Russia).

Pueden bajar un preprint de arXiv. La versión publicada es un poco más corta por límites de espacio, y está aquí: LNCS 9691:146-160.

Lo que hacemos en este trabajo es definir los autómatas afines. La idea surgió de un comentario que hice en una charla que dio Abuzer en mi grupo acerca de los autómatas cuánticos. La ganancia computacional que tenían estos autómatas parecía venir exclusivamente de las amplitudes negativas, entonces surgió la pregunta de si podríamos tener el mismo poder computacional simplemente usando un autómata probabilista con "probabilidades" negativas. Y así llegamos a las transformaciones afines: la idea es que un estado está representado por un vector cuyas componentes suman uno, sólo que no pedimos que sean positivas (como en un autómata probabilista). Luego usamos transformaciones afines (que mantienen la suma a uno) como matriz de transición. El resultado fue sorprendente ya que en el caso determinista, resultó ser más poderoso que los autómatas finitos cuánticos (y en el caso no determinista, igual).

Dejaré los slides una vez lo prepare para el simposio (que es en San Petersburgo del 9 al 13 de junio). Update: Aquí están.

Cabe aclarar que Abuzer es el especialista en autómatas (igual que Marcos Villagra, co-autor de este blog), mi campo principal es el cálculo lambda y la teoría de tipos... pero estuvo buena esta colaboración y espero ir aprendiendo más del tema.

Comenzando actividades

Hace casi un año que me mudé de vuelta a Asunción para iniciar mis actividades académicas. Me dijeron que el primer año resultaría duro y lo fue. Especialmente después de haber vivido casi ocho años en Japón y volver a acostumbrarme a mi propia cultura fue lo más difícil. Hasta este momento nunca me había dado cuenta de lo aculturado que estaba a Japón.

Actualmente estoy realizando un cambio en mis estudios y estoy aprovechando estos nuevos aires para incursionar en complejidad algebraica. Es un área de estudio que me siempre me provocó curiosidad y siempre disfruté estudiar. Ahora es una buena oportunidad para comenzar en esto. No significa que voy a dejar la computación cuántica, sino más bien, sería como un refuerzo que actuaría en sinergía con la computación cuántica. Los mismos conceptos aparecen en ambos como los tensores, los polinomios, y por supuesto, el álgebra abstracta.

Este año voy a estar muy concentrado en crear un grupo de investigación en teoría de la computación, el cual es un área (según mi entendimiento) inexistente en el Paraguay. Solo estamos dos personas que hacemos investigación en teoría de la computación. Espero poder cambiar eso en un futuro.

Por lo tanto estoy buscando estudiantes de grado y postgrado interesados en hacer teoría de la computación, en particular, las áreas de complejidad algebraica, computación cuántica y complejidad computacional clásica. Hay oportunidades de beca para estudiantes a tiempo completo, y nuestro consejo de ciencia y tecnología local ofrece todos los años becas de postgrado. Además, nuestro programa de postgraduación en Ciencias de la Computación es muy bueno, con expertos en diferentes áreas como bioinformática, optimización, ingeniería, computación científica y otros.

Voy a ir reportando avances de como vamos organizando el grupo. No quiero prometer publicaciones en el blog cada cierto tiempo estecífico, pero si voy a intentar cada tanto hacer una actualización. Es increíble como antes teníamos como una entrada en el blog cada semana, pero luego de graduarme y empezar a trabajar se hizo muy difícil escribir.

Este es un buen momento para volver a escribir.