23 de mayo de 2012

Escuela en Lenguajes Formales

Hay una escuela en teoría de la computación que se va a llevar a cabo en Tarragona, España. Se llama International Fall School in Formal Languages and Applications.  Aunque en el nombre dice "Lenguajes Formales", en el programa se pueden ver cursos bastantes variados como circuitos booleanos y máquinas de Turing. Estoy considerando muy seriamente asistir. Este año, exactamente en ese mismo lugar, se llevó a cabo la conferencia LATA'12. Un amigo fue a presentar un paper este año allí y quedó encantado con Tarragona.

Aprovecho también para avisar que por fin colgaron algunos videos de las presentaciones de QIP'12 en este link. Ya estuve mirando un par de videos y tienen muy buena calidad.

Bueno, espero que algunas personas puedan aprovechar la escuela que promete mucho. Ya me pensaré muy bien si asistir o no.


22 de mayo de 2012

Mini-reporte de TAMC'12

Ya estoy de vuelta de TAMC'12. La conferencia estuvo muy buena, y tengo que destacar los Turing Lectures que se llevaron a cabo. Abajo pongo algunas fotos. No pude estar en todas porque sole estuve hasta el viernes 18.

Abajo pueden ver un poco del lugar de la conferencia, la cual se llevó a cabo en el Institute of Software, Chinese Academy of Science.






John Hopcrof: Su presentación se tituló On the Impact of Turing Machines. Fué sobre la historia de las máquinas de Turing y evolución hasta nuestros días. Hizo principal énfasis en la robustez del modelo para el estudio de la computación. Recalcó también que sin ese modelo, probablemente el descubrimiento de la complejidad computacional se hubiera atrasado en uno 10 a 20 años.



Richard Karp: Su presentación se tituló Theory of Computation as an Enabling Tool for the Sciences. Un recuento histórico del departamente de ciencias de la computación de UC Berkeley y la evolución de las ciencias de la computación como una ciencia interdisciplinaria.



S. Barry Cooper: Su presentación se tituló From Turing Machine to Morphogenesis -- Forming and Informing Computation. Tengo que admitir que entre las presentaciones en las que participé, esta fue mi favorita. Un recuento histórico sobre la historia de Turing y su impacto actual en las ciencias.



Deyi Li: Su presentación se tituló Interaction and Collective Intelligence on the Internet. Así como el título lo indica, fué sobre inteligencia colectiva, en particular en redes sociales. Destacó como el estudio de las redes sociales da cuenta de nuevos fenómenos sociales en la actualidad.



Por último, este es un recuerdo que me llevo de la conferencia.


13 de mayo de 2012

De vuelta a Beijing

Estoy de vuelta viajando a Beijing para TAMC'12. Es para presentar este paper. Los slides se pueden descargar de aquí. Esta conferencia promete mucho, ya que varios científicos muy importantes estarán haciendo presentaciones en ocasión del año de Turing.


Espero que algunos hayan tenido la oportunidad de participar en LATIN'12 que fue en Arequipa, Perú. Tuvieron también una muy linda escuela en teoría de la computación. También hay WoLLIC'12 en Buenos Aires. Yo fuí a esa conferencia en el 2007 en Río de Janeiro. Muy buena conferencia, con temas muy interesentes, más enfocado en lógica y computabilidad. Y no se olviden de LATINCYPT este año en Santiago.

Muy buen año para latinoamérica en ciencias de la computación (teoría). Tres excelentes conferencias. Espero que muchos puedan aprovecharlas, porque LATIN es cada 2 años, y WoLLIC suele cambiar cada año. LATINCRYPT no sé.


6 de mayo de 2012

Linearidad en Lineal vs Linearidad en Lógica Lineal

Barbara Petit y yo hemos enviado un paper para revisión. En este trabajo, hacemos un análisis de la linealidad en el lambda cálculo algebraico lineal (Lineal), y la comparamos con la linealidad de lógica lineal.

En lógica lineal, una función es lineal, si utiliza una sola vez su argumento. Así, f(x)=x² no es lineal (ya que utiliza su argumento x dos veces), mientras f(x)=x+1 sí. En Lineal una función f(x+y) se toma como f(x)+f(y), imitando la definición de las funciones lineales en álgebra (o, tal es el objetivo, la multiplicación de matrices por vectores, como en computación cuántica).

En este nuevo paper definimos un sistema de tipos para Lineal (o para ser más precisos, para el fragmento de Lineal que sólo tiene sumas, ya que es la parte que nos interesa, y que además coincide con varios lenguajes no-deterministas). Este sistema de tipos caracteriza las superposiciones y la linealidad del lenguaje. Luego mostramos que este sistema se puede traducir en Sistema F con pares, el cual se corresponde con el fragmento no-lineal de IMELL (el fragmento intuisionista, multiplicativo, exponencial de la lógica lineal). Esto plantea la primera sorpresa: el cálculo Lineal se traduce en un fragmento no-lineal de la Lógica Lineal.

En realidad lo que sucede, es que Lineal se mantiene fiel a la computación cuántica, donde x+y representa una superposición de x e y, los cuales son atómicos, y una función que duplique su argumento, por ejemplo, es perfectamente válido, siempre y cuando sólo pueda duplicar elementos atómicos. Por tanto, f(x+y) se toma como f(x) + f(y) y no habrá problema en que f duplique su argumento. O sea, Lineal considera que todas sus funciones son lineales, no las fuerza a ser lineales, sólo las trata como tales, lo cual es necesario para evitar el clonado, operación prohibida en computación cuántica, y es suficiente ya que lo interesante en Lineal es que puede encodear operadores cuánticos, que son siempre lineales.

Update: el paper fue acceptado en WoLLIC 2012Acá dejo un post sobre eso.

Pueden bajar el paper libremente desde arXiv o desde su sitio final de publicación (si tienen acceso) en Springer.

Update 2: slides de un seminario pre-conferencia.