Complejidad computacional. STOC 2013

1. STOC es una de las principales conferencias que se celebran todos los años sobre teoría de la computación. La de este año es la edición nº 45. Es tradición en este blog seleccionar los papers más destacados, desde nuestro modesto punto de vista en este tipo de conferencias.

Este año, no lo vamos a hacer de momento. Si te interesa la lista completa, con enlaces a los papers que son accesibles en PDF puedes visitar este blog.

2. Sí me ha llamado la atención un paper sobre la ETH, que me interesa desde hace un cierto tiempo:

Strong ETH Holds For Regular Resolution
Chris Beck (Princeton University) and Russell Impagliazzo (UC San Diego).

Cómo no está accesible en PDF no lo he podido leer.  Ni siquiera sé que es Regular Resolution, cosa que estoy aprendiendo ahora mismo, entre otros gracias a este paper.

Bueno, ya está más o menos claro: Resolution es un método de demostración en lógica, que se puede dividir entre General y Regular Resolution.  Se han separado exponencialmente ambos métodos (no se las cotas exactas ahora mismo). Y en este paper seguramente demuestran que la strong exponential hypothesis se cumple también para el método de resolución regular. No se que consecuencias tiene esto. En cualquier caso es una proposición relativa a un método en concreto, no general.

He visto que el artículo de Wikipedia sobre la ETH está bastante más completo. Mañana lo leeré más en detalle y quizás añada algún comentario.

Actualización.

Añadimos la lista de papers+abstracts de la conferencia Complexity. Mucho quantum…

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: