Banear Elsevier

Les recomiendo este artículo en el blog de Tim Gowers (un medalla Fields y blogger), donde expresa su preocupación sobre las revistas de Elsevier y el apoyo de esta editorial a los proyectos de ley estadounidenses SOPA, PIPA y Research Works Act (esta última es un proyecto para prohibir las publicaciones científicas estadounidenses en revistas de libre acceso).

Hay una declaración de intención donde, hasta ahora, 460 científicos han (hemos!) dado su apoyo diciendo que o bien no van a publicar, o no van a hacer reviews, o no van a participar en la edición de revistas de esa editorial (o ninguna de las 3), hasta que cambie sus políticas. Se pueden ver algunas personalidades muy reconocidas entre los firmantes, como por ejemplo Jean-Louis Krivine, entre muchos otros.

Update: Agrego más cosas al post.

En el post de Tim Gowers menciona otros 3 puntos en contra de Elsevier, que resumidamente son:

1. Precios extremadamente elevados

2. La justificación de esos precios con que te tenés que suscribir a todas sus revistas en algún tema, o a ninguna (no podés elegir a qué revistas suscribirte)

3. Cuando una biblioteca trata de negociar el precio, Elsevier directamente les corta el acceso a todas sus publicaciones.

Y lo más importante: los papers los escriben científicos (no pagados por Elsevier), los referean los mismos científicos (tampoco se recibe retribución por eso) y en la mayoría de los casos, los editan los mismos científicos, también gratuitamente. Porqué Elsevier luego les vende las publicaciones a las mismas instituciones que pagan a esos científicos? Pues no tiene sentido alguno. Hace mucho tiempo, el trabajo de Elsevier era distribuir las publicaciones, así llegaba a las distintas universidades y centros de investigación. Hoy en día, con Internet, no sólo es innecesario su trabajo, es contraproducente, ya que quien no haya pagado el acceso, no puede acceder a la publicación (y Elsevier en particular tiene reglas muy duras en cuanto a no permitir a los autores poner una copia gratuitamente en la web).

Por eso están proliferando cada vez más las publicaciones de libre acceso, como por ejemplo Logical Methods in Computer Science (hay muchas más, sólo menciono el ejemplo más relevante a mi trabajo), que cuenta con un cuerpo editorial del más alto nivel en el área, tiene un proceso de review muy riguroso, y la publicación se hace online, de libre acceso y con licencia Creative Commons. Hay muchísimas revistas, en casi cualquier área de la ciencia, de acceso gratuito. Aquí dejo un sitio que se encarga de listarlas.

Y la pregunta obligada es: Realmente necesitamos a Elsevier?

Logic and interactions 2012

Desde el 30 de Enero al 2 de Marzo, se llevará a cabo en la ciudad de Marsella (Francia) el evento Lógica e interacciones. Se trata de un evento de 5 semanas que reunirá investigadores en muchas áreas de lógica computacional.

En particular la cuarta semana, del 20 al 24 de Febrero, estará dedicada a "Enfoques Cuantitativos". Los organizadores de dicha semana son Michele Pagani, Simon Perdrix, Peter Selinger y Christine Tasson. Habrá cursos dictados por Thomas Ehrhard, Elham Kashefi, Prakash Panangaden y Christine Tasson. Además se contará con numerosos oradores invitados de renombre, y algunas contribuciones. Yo envié una contribución, la cual fue aceptada y la presentaré el jueves 23 a las 11:20. Aquí dejo los datos de mi presentación (la versión en inglés la pueden consultar en la página):

Título: 
Equivalencia entre proposiciones y pruebas
(trabajo conjunto con Gilles Dowek)

Resumen (traducción):

Sabemos que las proposiciones A∧B y B∧A son equiprobables: si una es probable, la otra también lo es, sin embargo no tienen la misma prueba. Aquí diseñamos un sistema de prueba tal que tengan la misma prueba, o sea, tomamos el cociente del conjunto de proposiciones por la relación generada por la conmutatividad de la conjunción, y definimos pruebas para elementos en este cociente. El cálculo obtenido es similar al fragmento aditivo de los cálculos algebraicos, más un proyector no determinístico.

Update: Los slides.

Update: Una versión mucho más desarrollada y terminada de este trabajo, fue aceptado en LSFA 2012. Aquí dejo el respectivo post.

Preparación para SODA 2012

El martes 17 de enero comienza SODA'12 en Kyoto. El hotel tiene muy linda pinta. Queda más o menos a 1 hora de camino desde donde vivo, asi que pienso ir y venir durante los 3 días que dure. Voy a intentar hacer un mini-reporte sobre los 3 días más adelante. Además voy a llevar mi super cámara Nikkon.

Voy a estar principalmente enfocado en las presentaciones sobre comunicación. Hay algunas muy interesantes también relacionadas a streaming. Sobre computación cuántica solo va a haber una presentación de Francois Le Gall sobre multiplicación de matrices.

Para el viaje en tren de 1 hora (2 horas ída y vuelta), me estoy llevando el libro Algebraic Complexity Theory.

Back Online!

Bueno, ya era hora de escribir algo de vuelta. Mucho pasó desde la última entrada. En particular, el fantástico anuncio de CERN sobre sus últimos experimentos en búsqueda del bosson de Higgs. Alguno siempre me pregunta por qué es tan importante descubrir esa partícula. Yo trato de explicar en los términos que yo entiendo, porque no soy físico. Este vídeo es fabuloso. Mejor que esto ya no se puede explicar. Es un poco largo.

Después también la conferencia QIP 2012 que se llevó a cabo en Montreal en diciembre. Lástima que este año no colgaron los videos en la página web como en años anteriores. Aún así, hay un excelente resumen en The Quantum Pontiff.

También, los últimos avances después de más de 20 años en multiplicación de matrices bien reportado en Shtetl Optimized.

Lo que me mantuvo ocupado, en especial los últimos 2 meses, es el nuevo paper en el que estaba trabajando. De hecho, ya había dado un pista en este post anterior. Es sobre una nueva técnica para encontrar cotas inferiores para protocolos de comunicación cuántica. En este post había explicado el modelo de comunicación. Bueno, después de mucho, mucho (y mucho) trabajo, por fin pude hacer lo que me propuse.

Uno de los problemas principales en esta área era demostrar un gap en la complejidad para modelos de comunicación con 3 o más jugadores. Un gap quiere decir, encontrar alguna función que clásicamente requiera ≥ X recursos computacionales (tiempo, espacio, etc), y quánticamente requiera a lo más estrictamente menor que X recursos computacionales. Por ejemplo, en búsqueda no-estructurada sabemos que clásicamente requerimos Ω(n) accesos a un oráculo, pero O(√n) accesos a un oráculo cuántico. Entonces acá hay un gap cuadrático.

En el caso de comunicación entre 2 jugadores, ya tenemos varios gaps exponenciales y cuadráticos. Para 3 o más jugadores no teníamos nada. Y de hecho este es un problema bastante difícil, principalmente porque las ténicas para cotas inferiores en modelos clásicos de multiparty communication son generalmente muy débiles, i.e., las cotas inferiores no son óptimas, y muchas veces están lejos de ser óptimas. Entonces ¿cómo hacer para demostrar un gap en comunicación multiparty? El truco está primero en relajar el modelo, por ejemplo, en lugar de considerar modelos de comunicación con bounded-error, considerar un modelo no-determinístico. Segundo, tener una nueva técnica.

Eso fue lo que hice en este trabajo. Primero consideramos un modelo de comunicación no-determinístico, y acotamos por arriba y por abajo utilizando el concepto de tensor rank. Esto luego lo aplicamos al problema de multiplicación de matrices y pudimos sacar un gap super-polinomial, el primero en multiparty communication.

Generalmente estos modelos no-determinísticos no son realistas, pero muchas veces se usan para hacer predicciones en modelos reales. Por ejemplo, P vs NP, i.e., tiempo determinístico vs tiempo no-determinístico. En este trabajo también hicimos algunas aplicaciones a comunicaciones cuánticas exactas, i.e., donde la respuesta se obtiene con probabilidad 1.

Al final lo mandé a una conferencia, y ahora estoy preparando la versión full para subir a arXiv y a ECCC y preparar la versión journal. Apenas lo tengo lo pondré aquí.

Actualización(14/Ene/2012): Aquí está la versión en ECCC.