23 de julio de 2013

LATIN 2014

La conferencia LATIN toca este año en Montevideo, Uruguay. Esta es la única conferencia en Teoría de la Computación en Latinoamérica, o mejor dicho, la única que se realiza "exclusivamente" en Latinoamérica. Hay otras conferencia que de tanto en tanto se hacen en Latinoamérica como WoLLIC. Además, LATIN abarca todas las áreas de la teoría de la computación.

Siempre LATIN tiene muy buen nivel de presentaciones. Así que es para no perderse. Sin embargo, lastimosamente este año no viene acompañado de una escuela de computación como fue en la edición anterior en Perú.

19 de julio de 2013

Autor se presenta


Hola estimados lectores de Computación cuántica. Es probable que desde un tiempo a esta parte hayan notado mi nombre en la lista de autores.
Con este post quiero develar el misterio y contarles las áreas y los temas de investigación en los cuales trabajo para darles una idea de cuales serán los tópicos que trataré en futuros posts.

Soy doctorando en el Grupo de Lógica y Teoría de la Computabilidad del Dpto. de Computación de la FCEyN-UBA. El objetivo de mi tesis es estudiar aspectos de la computación cuántica y de fundamentos de la física cuántica, desde el punto de vista de la teoría de la computabilidad y la teoría de la aleatoriedad algorítmica.

Mucho más concretamente, actualmente estoy trabajando en dos temas. El primero consiste en la aplicación de la complejidad de Kolmogorov (tanto la clásica como algunas de sus definiciones usando formalismos cuánticos) a la búsqueda de cotas inferiores en query complexity (tanto quantum como randomized).
El segundo tiene que ver con estudiar algunos de los No-go theorems de la cuántica (principalmente Bell y Kochen-Specker) y ver que se puede decir, en términos de computabilidad o de algunas de las nociones de aleatoriedad algorítmica, de la secuencia de resultados de mediciones (codificados apropiadamente con bits) en experimentos certificados por estos teoremas.

En futuros posts daré breves introducciones a estos temas y citare las referencias que acá omití.

¡Saludos!

18 de julio de 2013

A long time ago in a galaxy far far away....

Mi última entrada fue enero. No me gusta dar excusas pero si tengo unas muy buenas.

Primero, mas o menos desde Diciembre 2012 hasta finales de Febrero 2013 estuve exclusivamente trabajando en mi tesis. Para los que ya pasaron por esta etapa conocen bien lo que involucra. Bueno, al final entregué mi tesis y defendí en Marzo de 2013 (aunque ya no recuerdo la fecha exacta). El enlace de descarga lo pueden encontrar aquí. Me gusta decir que mi tesis (o disertación para algunos) está divida en dos partes: 1) Algoritmos y 2) cotas inferiores. Esas son las dos grandes partes en que podríamos dividir el área de circuit complexity. En la primera parte estudié una técnica de construcción de algoritmo llamada quantum walks, tema sobre el cual discutí aquí. La segunda parte consistió en un estudio sobre una técnica muy común para probar cotas inferiores de algoritmos llamada communication complexity el cual también lo discutí aquí. La tesis también tiene un conjunto de apéndices que se puede utilizar para empezar a estudiar estos temas, por si a alguien le interesa. En particular, hay una demostración del Yao's Minimax Lemma para algoritmos Montecarlo que no aparece en ningún otro lado. En el paper original de Yao, no aparece tal demostración, aunque el autor dice que no es difícil. Aunque es cierto que no es, me hizo pensar bastante para poder demostrar.

Segundo, después de mi graduación, empecé inmediatamente a trabajar de postdoc en la Universidad de Fukui bajo la supervisión de Tomoyuki Yamakami. Mi proyecto de investigación está principalmente en Teoría de Complejidad Computacional Estructural, con énfasis en sistemas de pruebas interactivos y criptografía que toca aspectos de computación clásica y cuántica. Este es un proyecto financiado por la Japan Society for the Promotion of Science (JSPS) del cual yo soy actualmente fellow. Apenas llegué en Abril estoy trabajando en este proyecto y al mismo tiempo empezando a manejar estudiantes y organizar seminarios.

Algo muy cierto que uno no se da cuenta cuando es estudiante es que todo lo que tus profesores te cuentan que sucederá una vez te gradúes es cierto. Ahora estoy mucho más ocupado que antes y como estoy en un proyecto de investigación tengo que si o sí tener resultados en forma periódica y en corto plazo. Esto pone bastante presión, algo que tenía muy poco cuando era estudiante. En particular, ahora que soy un investigador independiente, tengo que manejar mi propio presupuesto, lo cual implicar escribir propuestas de investigación para pedir financiamiento. Porque sin eso, literalmente , no se puede hacer nada, nada de viajes, nada de libros, etc. Ahora tengo que pensar en todo eso, lo cual no me preocupaba en mi época de estudiante. Por suerte no tengo que estar dando clases, lo cual también puede cambiar en cualquier momento. Por lo tanto, voy a aprovechar el tiempo que tengo ahora.

Pero en síntesis, es un buen cambio, y es un tipo de vida al que todos los que pretendemos hacer la carrera de científicos deberíamos saber manejar.

Bueno, voy a empezar a ponerme las pilas para mantener el ritmo de publicación que tenía en el blog. Tengo un paper que estoy por subir al arXiv y de a poco voy a ir contando sobre mis proyectos de investigación actuales apenas empiece a tener cosas sobre las que pueda compartir en público.

9 de julio de 2013

La probabilidad de los sistemas no-confluentes

El paper que comenté en el post "Escapando al no-determinismo" fue aceptado en el 9no workshop internacional "Developments in computational models", un workshop de un día que este año se hace por primera vez en Argentina (primera vez fuera de Europa!).

El programa del workshop ya está publicado online.

Los detalles del paper lo pueden ver en el post anterior, donde también dejé un link al paper, y la versión completa con todas las pruebas.

Nos vemos en Buenos Aires.