| michalis yannakakis | |
|---|---|
| Griego Μιχάλης Γιαννακάκης | |
| Fecha de nacimiento | 13 de septiembre de 1953 (69 años) |
| Lugar de nacimiento | Atenas , Grecia |
| País | |
| Esfera científica |
teoría de la complejidad computacional , bases de datos |
| Lugar de trabajo | Universidad de Colombia |
| alma mater | Universidad Técnica Nacional de Atenas |
| consejero científico | Geoffrey Ullman |
| Premios y premios |
Premio al miembro distinguido del personal técnico de Bell Labs ( 1985 ) Premio de oro del presidente de Bell Labs ( 2000 ) Premio Knuth ( 2005 ) |
Michalis Yannakakis ( griego Μιχάλης Γιαννακάκης , inglés Mihalis Yannakakis ; nacido el 13 de septiembre de 1953 en Atenas , Grecia ) es un informático griego , profesor de la Universidad de Columbia ( Nueva York , EE . UU .). Conocido por su trabajo en teoría de la complejidad computacional , bases de datos y otros campos relacionados. Ganador del Premio Knuth ( 2005 ). Miembro de la Academia Nacional de Ciencias de EE . UU. (2018) [1] .
Michalis Giannakakis nació en Atenas el 13 de septiembre de 1953 y para su primera educación asistió al Varvakio Experimental Gymnasium (griego: Βαρβάκειο Πειραματικό Γυμνάσιο) en Psychiko (Atenas).
En 1975 se graduó de la Universidad Técnica Nacional de Atenas con una licenciatura en ingeniería eléctrica y en 1979 recibió un doctorado en informática de la Universidad de Princeton ( EE.UU. ). Su disertación se tituló " La complejidad de los problemas de máximo subgrafo ". [2]
En 1978, Michalis Giannakakis se unió a Bell Lab Corporation ( Murray Hill , Nueva Jersey , EE . UU .) y en 1991-2001. Fue director de la División de Investigación de Fundamentos de Tecnología de la Información. Luego dejó Bell Laboratories y se unió a Avaya Labs. Allí, Giannakakis fue director de la División de Investigación de Fundamentos de Tecnología de la Información hasta 2002 .
En 2002 , Giannakakis asumió como profesor de informática en la Universidad de Stanford , donde permaneció hasta 2003 .
Desde 2004 hasta el presente ha sido profesor de informática en la Universidad de Columbia .
De 1992 a 2003 _ Giannakakis formó parte del consejo editorial de SIAM Journal on Computing (SICOMP ) de 1998 a 2003 . fue su redactor jefe. En 1986 - 2000 _ también formó parte del consejo editorial de Journal of the Association for Computing Machinery . Michalis Giannakakis es miembro de los consejos editoriales de varias otras revistas, incluidas Journal of Computer and System Sciences , Journal of Combinatorial Optimization y Journal of Complexity . También se ha desempeñado en comités de conciliación y presidido varias conferencias, como el Simposio ACM sobre Principios de Sistemas de Bases de Datos (PODS) y el Simposio IEEE sobre Fundamentos de Ciencias de la Computación.
Hasta noviembre de 2015 , las publicaciones científicas de Michalis Giannakakis han sido citadas unas 27 000 veces y su índice h es 86. [3]
Michalis Giannakakis es conocido por sus contribuciones a la informática , en áreas como la teoría de la complejidad computacional , la teoría de bases de datos , la verificación y prueba automatizadas y la teoría algorítmica de grafos .
Un lugar especial entre los valiosos logros del científico en el campo de la teoría de la complejidad lo ocupan dos trabajos clave sobre los temas de la teoría de las pruebas probabilísticamente verificables y la complejidad de la aproximación . En 1988 , Michalis Giannakakis y Christos Papadimitriou presentaron las definiciones de las clases de complejidad Max-NP y Max-SNP (que es una subclase de Max-NP) en el Simposio anual sobre teoría de la computación financiado por la Association for Computing Machinery (AUT) , que contiene un varios problemas de optimización interesantes. Giannakakis y Papadimitriou demostraron que estos problemas tienen algún error limitado. Con la ayuda de estos hallazgos, fue posible explicar la falta de progreso observada en la comunidad de investigación en el estudio de la aproximabilidad de una serie de problemas de optimización, incluido el problema de " 3-satisfacibilidad " , el problema de conjuntos independientes y el Problema del viajante de comercio . [cuatro]
En 1993 , en el simposio regular AVT sobre la teoría de la computación, Michalis Giannakakis y Karsten Lund presentaron una serie de conclusiones importantes sobre el tema de las aproximaciones computacionales . Estos resultados mostraron la dificultad de calcular de manera eficiente las soluciones aproximadas para una serie de problemas de minimización, como el caso de la coloración de gráficos y el problema de cobertura de conjuntos . Dada la improbabilidad de que tales problemas NP-difíciles se resuelvan de manera óptima en tiempo polinomial , se han hecho muchos intentos para desarrollar soluciones aproximadas eficientes para ellos. Los resultados obtenidos por Giannakakis y Carsten demostraron que era poco probable que se lograra este objetivo. [5]
En el campo de la teoría de bases de datos, la principal contribución de Michalis Giannakakis es el inicio de la investigación en bases de datos acíclicas y bloqueo no bifásico. Los esquemas de base de datos acíclicos son esquemas que contienen una dependencia de conexión acíclica y un conjunto de dependencias funcionales. [6] Varios investigadores, incluido Giannakakis, han notado la utilidad de estos esquemas, demostrando las muchas propiedades útiles que tienen: la capacidad de resolver muchos problemas basados en esquemas acíclicos en tiempo polinomial, a pesar de que el problema podría ser NP -completa para otros esquemas. [7]
Fue galardonado con el Premio Knuth ( 2005 ) por la importancia, la influencia y el alcance asombroso de su contribución a los fundamentos teóricos de la computación, y también recibió dos premios de Bell Labs: Premio Miembro Distinguido del Personal Técnico ( 1985 ) y Premio de Oro del Presidente ( 2000 ). Es miembro de la Association for Computing Machinery y un centro de investigación en Bell Labs .
| Ganadores del premio Knuth | |
|---|---|
| |