Premio Gödel

Premio Gödel Institución Fundación: 1993, hasta la actualidad. Tipo de unidad: Concurso anual.

El Premio Gödel es un premio que se entrega a autores de artículos relacionados con teoría de la computación. El nombre del premio se debe al matemático Kurt Gödel, y es otorgado por la European Association for Theoretical Computer Science (EATCS) y el Special Interest Group on Algorithms and Computation Theory de la Association for Computing Machinery (ACM).

El Premio Gödel se entrega anualmente desde 1993, ya sea en el STOC (ACM Symposium on Theory of Computing), una de las principales conferencias de norteamérica en el área de informática teórica, o bien en el ICALP (International Colloquium on Automata, Languages, and Programming), una de las principales conferencias europeas en la misma área. Aparte de la distinción, incluye un bono de 5000 dólares. Como requisito para recibir el premio, el artículo ganador debe haber sido publicado en una revista científica hace máximo 14 años atrás (anteriormente eran sólo 7 años).

Instituciones que lo otorgan

European Association for Theoretical Computer Science

La European Association for Theoretical Computer Science (EATCS) es una organización internacional fundada en 1972, cuyo objetivo es facilitar el intercambio de ideas y resultados entre informáticos teóricos, así como estimular la cooperación entre las comunidades teórica y práctica de ciencias de la computación.

Las principales actividades de la EATCS son:

• Organizar el ICALP (International Colloquium on Automata, Languages and Programming, o Coloquio Internacional de Autómatas, Lenguajes y Programación);
• Publicar una serie de monogramas y textos relacionadas con ciencias de la computación;
• Publicar el Boletín de la EATCS;
• Publicar la revista científica Theoretical Computer Science.

Association for Computing Machinery (ACM)

La Association for Computing Machinery (ACM) fue fundada en 1947 como la primera sociedad científica y educativa acerca de la Computación. Publica varias revistas y periódicos científicos relacionados con la computación; patrocina conferencias en varias areas del campo (principalmente el SIGGRAPH y el SIGCOMM) y otros eventos relacionados con las ciencias de la computación como por ejemplo el ACM International Collegiate Programming Contest (ICPC) . Publica una extensiva Biblioteca digital y una referencia de la literatura de la computación. La ACM también ofrece seguros y otros servicios a sus miembros de los Estados Unidos.

Tiene presencia en más de 100 países.

Los primeros pasos de lo que más tarde sería la ACM se dieron en 1947, durante un simposio sobre computación en la Universidad de Harvard, cuando su fundador, Edmund C. Berkeley, se convenció del verdadero potencial multidisciplinar que esta tecnología computacional brindaba. Allí gracias al contacto con gran parte de la comunidad científica formada en torno a este campo. Berkeley, impresionado tras el simposio, decidió formar una asociación al margen de cualquier institución académica o gubernamental que se ocupara específicamente en materia de computación, así surgió la Eastern Association of Computing Machinery (EACM). La sociedad estaba compuesta en un principio por unos cuantos asistentes al simposio, interesados en mantenerse al día en las nuevas tecnologías. Pero el verdadero éxito de la organización devino realmente cuando Berkeley emitió un comunicado entre todos sus miembros, citando unas palabras del por entonces director del MIT Center of Analysis, Samuel Cadwell, pronunciadas durante el simposio de Harvard. Cadwell se mostraba preocupado por la labor de encubrimiento que el propio ejército de los Estados Unidos estaba llevando a cabo con las investigaciones realizadas durante la segunda Guerra Mundial, y en su conferencia hizo un llamamiento a la libre difusión del conocimiento y al libre intercambio de información entre los investigadores de todas las áreas relacionadas con la computación. Berkeley se sumó a esta iniciativa, y la propuso como elemento motriz de su asociación con el fin de que todos sus miembros pudieran obtener beneficios profesionales. Muchos especialistas y directores de otras asociaciones relacionadas con la tecnología, vieron el proyecto con muy buenos ojos y se ofrecieron para colaborar en él. En agosto de 1948 ya eran 350 miembros, provenientes de una extensión geográfica tal, que Berkeley consideró que el Eastern, podía ser eliminado del nombre . Desde entonces hasta nuestros días, la ACM ha constituido un foro de debate en el que han participado especialistas de todo el mundo y de todas las áreas del conocimiento, legándonos un ingente material bibliográfico que puede ser consultado en su Librería Digital . La Association of Computing Machinery ha adquirido un puesto preponderante como referente académico debido a dos conceptos fundamentales y visionarios en los que se basó su fundación: la voluntad de libre intercambio y el carácter multidisciplinar de sus investigaciones.

La ACM publica varias revistas y libros. Entre sus publicaciones habituales tenemos:

• Communications of the ACM
• netWorker
• Mobile Networks and Applications (MONET)
• Journal of Graphics Tools
• Journal of Experimental Algorithmics (JEA)
• Distributed Computing
• Interactions
• Multimedia Systems.

Para su trabajo está organizada en 34 Grupos de Interés Especial, (SIGs o Special Interest Groups, en inglés), uno de ellos el Special Interest Group on Algorithms and Computation Theory (SIGACT), es el encargado por la ACM de coordinar y entregar el Premio Gödel.

Ganadores

• 1993 - László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran y Charles Rackoff, por el desarrollo de sistemas de demostración interactivos.
• 1994 - Johan Håstad, por encontrar una cota inferior exponencial en función del tamaño de profundidad-constante de un circuito booleano para la función paridad.
• 1995 - Neil Immerman y Róbert Szelepcsényi, por el Teorema de Immerman-Szelepcsényi.
• 1996 - Mark Jerrum y Alistair Sinclair, por el trabajo en las Cadenas Markov y la aproximación de el permanente.
• 1997 - Joseph Halpern y Yoram Moses, por definir una noción formal de "conocimiento" en ambientes distribuídos.
• 1998 - Seinosuke Toda, por el Teorema Toda, con el cual mostró una conexión entre las Soluciones de Conteo (PP) y la alternancia de cuantificadores.
• 1999 - Peter Shor, por el Algoritmo de Shor para factorizar números en tiempo polinomial en un computador cuántico
• 2000 - Moshe Y. Vardi y Pierre Wolper, por trabajar en el chequeo modelo con autómatas finitos.
• 2001 - Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan y Mario Szegedy, por el Teorema PCP y sus aplicaciones a la resistencia de aproximación.
• 2002 - Géraud Sénizergues, por demostrar que la equivalencia de autómatas de pila deterministas es decidible.
• 2003 - Yoav Freund y Robert Schapire, por el algoritmo AdaBoost.
• 2004 - Maurice Herlihy, Mike Saks, Nir Shavit y Fotios Zaharoglou, por aplicar topología a la teoría de computación distribuida.
• 2005 - Noga Alon, Yossi Matias y Mario Szegedy, por su contribución fundacional a los Streaming Algorithms.
• 2006 - Manindra Agrawal, Neeraj Kayal, Nitin Saxena, por el Test de primalidad AKS
• 2007 - Alexander Razborov y Steven Rudich, por las demostraciones naturales
• 2008 - Shanghua Teng y Daniel Spielman, por el análisis Smoothed de logaritmos
• 2009 - Omer Reingold, Avi Wigderson y Salil Vadhan, por el análisis de SL (complejidad)
  
• 2010 - Sanjeev Arora, Joseph S. B. Mitchell, por su descubrimiento simultáneo de un Esquema de Aproximación tiempo-polinomial para el Problema del Vendedor Viajero.
  

Enlaces externos

Página del premio con la lista de ganadores