De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Mihalis Yannakakis
Mihalis Yannakakis 2006.jpg
Mihalis Yannakakis
Nació( 13 de septiembre de 1953 )13 de septiembre de 1953 (67 años)
Atenas , Grecia
NacionalidadGriego - Americano
alma materUniversidad Técnica Nacional de Atenas Universidad de
Princeton
PremiosPremio Knuth (2005)
Carrera científica
Los camposCiencias de la Computación
InstitucionesUniversidad de Colombia
Asesor de doctoradoJeffrey Ullman

Mihalis Yannakakis (en griego : Μιχάλης Γιαννακάκης ; nacido el 13 de septiembre de 1953 en Atenas , Grecia ) [1] es profesor de informática en la Universidad de Columbia . Se destaca por su trabajo en complejidad computacional , bases de datos y otros campos relacionados. Ganó el premio Donald E. Knuth en 2005. [2]

Educación y carrera [ editar ]

Yannakakis nació en Atenas, Grecia en 1953 y asistió a la escuela secundaria Varvakeio para su educación temprana. Se graduó de la Universidad Técnica Nacional de Atenas en 1975 con un diploma en Ingeniería Eléctrica y luego obtuvo su Ph.D. en Ciencias de la Computación de la Universidad de Princeton en 1979. [1] Su disertación se tituló "La complejidad de los problemas máximos de subgrafos". [3]

En 1978 se incorporó a Bell Laboratories y se desempeñó como Director del Departamento de Investigación de Principios de Computación desde 1991 hasta 2001, cuando dejó los laboratorios Bell y se unió a Avaya Laboratories. Allí se desempeñó como Director del Departamento de Investigación de Principios de Computación hasta 2002. [1]

En 2002 se incorporó a la Universidad de Stanford, donde fue profesor de Ciencias de la Computación, y se fue en 2003 para incorporarse a la Universidad de Columbia en 2004, donde actualmente se desempeña como Profesor de Ciencias de la Computación Percy K. y Vida LW Hudson . [1]

De 1992 a 2003, Yannakakis formó parte del comité editorial de SIAM Journal on Computing y fue editor en jefe entre 1998 y 2003. También fue miembro del comité editorial del Journal of the ACM de 1986 a 2000. [1] Otros miembros de la junta editorial incluyen el Journal of Computer and System Sciences , el Journal of Combinatorial Optimization y el Journal of Complexity. También se ha desempeñado en comités de conferencias y ha presidido varias conferencias, como el Simposio ACM sobre principios de sistemas de bases de datos y el Simposio IEEE sobre fundamentos de la informática . [1]

Hasta junio de 2020, sus publicaciones han sido citadas cerca de 35.000 veces y tiene un índice h de 93. [4]

Investigación [ editar ]

Yannakakis es conocido por sus contribuciones a la informática en las áreas de teoría de la complejidad computacional , teoría de bases de datos , verificación y pruebas asistidas por computadora y teoría de grafos algorítmicos .

Entre sus contribuciones a la teoría de la complejidad se encuentran dos artículos sobre la teoría PCP y sobre la dureza de aproximación . En el Simposio Anual ACM sobre Teoría de la Computación de 1988, Yannakakis y Christos Papadimitriou presentaron las definiciones de las clases de complejidad Max-NP y Max-SNP. Max-NP y Max-SNP (que es una subclase de Max-NP) contienen una serie de problemas de optimización interesantes, y Yannakakis y Papadimitriou demostraron que estos problemas tienen algún error acotado. Estos hallazgos pudieron explicar la falta de progreso que se había visto en la comunidad de investigación sobre la aproximabilidad de una serie de problemas de optimización, incluido 3SAT , el problema del conjunto independiente.y el problema del vendedor ambulante . [5]

Yannakakis y Carsten Lund presentaron una serie de hallazgos con respecto a la dureza de las aproximaciones de computación en el Simposio Anual de ACM sobre Teoría de la Computación de 1993. Estos hallazgos demostraron la dificultad de calcular de manera eficiente soluciones aproximadas a una serie de problemas de minimización, como la coloración de gráficos y la cobertura de conjuntos. . Dado el improbable escenario de que los problemas NP difíciles , como el color de los gráficos y la cobertura de conjuntos, se resolverían de manera óptima en tiempo polinomial , se han realizado muchos intentos de desarrollar soluciones de aproximación eficientes para ellos; los resultados obtenidos por Yannakakis y Carsten demostraron la improbabilidad de lograr esta tarea. [6]

En el área de teoría de bases de datos , sus contribuciones incluyen el inicio del estudio de bases de datos acíclicas y de bloqueo no bifásico. Los esquemas de base de datos acíclicos son esquemas que contienen una única dependencia de unión acíclica (una dependencia de unión es una relación que gobierna la unión de tablas de la base de datos) y una colección de dependencias funcionales; [7] varios investigadores, incluido Yannakakis, señalaron la utilidad de estos esquemas demostrando las muchas propiedades útiles que tenían: por ejemplo, la capacidad de resolver muchos problemas basados ​​en esquemas acíclicos en tiempo polinomial, mientras que el problema podría fácilmente haberse sido NP-completo para otros esquemas. [8]

Con respecto al bloqueo que no es de dos fases , Yannakakis demostró cómo el conocimiento sobre la estructura de una base de datos y las formas de las diversas transacciones ejecutadas en ellas podría usarse para establecer si una política de bloqueo en particular es segura o no. Las políticas de bloqueo de dos fases (2PL) comúnmente utilizadas constan de dos etapas - para bloquear y desbloquear entidades respectivamente - y para evitar tal política es necesario imponer alguna estructura a las entidades de una base de datos; Los resultados de Yannakakis muestran cómo, al elegir un hipergráficoasemejándose a la estructura de restricción de consistencia de una base de datos, una política de bloqueo que visita entidades a lo largo de las rutas de este hipergráfico será segura. Esta política no tiene por qué ser de dos fases y estas políticas pueden clasificarse de acuerdo con la conectividad del hipergráfico mencionado anteriormente, siendo las políticas 2PL solo una instancia particular de estas. [9] Yannakakis continuó mostrando que para la clase natural de pólizas de bloqueo seguro (pólizas L), la ausencia de interbloqueos se determina únicamente en el orden en que las transacciones acceden a las entidades, y de esto se derivan condiciones simples que garantizarían la libertad. de puntos muertos para una política L. [10]

También ha contribuido al área de verificación y pruebas asistidas por computadora, donde sentó los rigurosos fundamentos algorítmicos y teóricos de la complejidad del campo. Algunas de sus contribuciones incluyen el diseño de algoritmos eficientes de memoria para la verificación de propiedades temporales de programas de estado finito, [11] determinar la complejidad de probar si los programas satisfacen sus especificaciones expresadas en lógica temporal de tiempo lineal , [12] y verificar que un modelo con restricciones de tiempo satisface una propiedad temporal dada. [13]Junto con Alex Groce y Doron Peled, presentó la Verificación de modelos adaptables, que muestra que cuando existen inconsistencias entre un sistema y el modelo correspondiente, los resultados de la verificación se pueden utilizar para mejorar el modelo. [14] También ha contribuido a la investigación sobre los gráficos de secuencia de mensajes (MSC), donde se demostró que la realizabilidad débil es indecidible para los gráficos MSC delimitados y que la realización segura está en EXPSPACE , junto con otros resultados interesantes relacionados con la verificación de Gráficos MSC. [15]

Premios y reconocimientos [ editar ]

Yannakakis es miembro tanto de la Academia Nacional de Ingeniería como de la Academia Nacional de Ciencias . Fue galardonado con el séptimo premio Knuth por sus contribuciones a la informática teórica. [2] También ha sido galardonado con el premio Bell Labs Distinguished Member of Technical Staff Award y el Bell Labs President's Gold Award, en 1985 y 2000 respectivamente. Es miembro de la ACM y también miembro de Bell Laboratories . [1] Fue elegido miembro de la Academia Estadounidense de Artes y Ciencias (AAAS) en 2020. [16]

Referencias [ editar ]

  1. ^ a b c d e f g Columbia University: CV: Mihalis Yannakakis (consultado el 12 de noviembre de 2009)
  2. ^ a b Premio Knuth Archivado el 28 de enero de 2012 en Wayback Machine (consultado el 3 de junio de 2015)
  3. ^ The Mathematics Genealogy Project - Mihalis Yannakakis (consultado el 9 de diciembre de 2009)
  4. ^ "Registro académico de Googel de M. Yannakakis" .
  5. ^ Christos Papadimitriou, Mihalis Yannakakis, Clases de optimización, aproximación y complejidad, Actas del vigésimo simposio anual de ACM sobre teoría de la computación, p.229-234, 2-4 de mayo de 1988.
  6. ^ Carsten Lund, Mihalis Yannakakis, Sobre la dureza de aproximar los problemas de minimización, Actas del vigésimo quinto simposio anual ACM sobre teoría de la computación, p.286-293, 16-18 de mayo de 1993.
  7. ^ Catriel Beeri, Ronald Fagin, David Maier, Alberto Mendelzon, Jeffrey Ullman, Mihalis Yannakakis, Propiedades de los esquemas de bases de datos acíclicos, Actas del decimotercer simposio anual de ACM sobre teoría de la computación, p.355-362, 11-13 de mayo de 1981.
  8. ^ Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis, Sobre la conveniencia de los esquemas de bases de datos acíclicos, Revista de la ACM, v.30 n. 3, p.479-513, julio de 1983.
  9. ^ Mihalis Yannakakis, Una teoría de las políticas de bloqueo seguro en sistemas de bases de datos, Journal of the ACM, v.29 n.3, p.718-740, julio de 1982.
  10. ^ Mihalis Yannakakis, Libertad de los puntos muertos de las políticas de bloqueo seguro, SIAM J. on Computing 11 (1982), 391-408.
  11. ^ C. Courcoubetis, M. Vardi, P. Wolper, M. Yannakakis, Algoritmos eficientes de memoria para la verificación de propiedades temporales, Métodos formales en el diseño de sistemas, v.1 n.2-3, p.275-288, Oct 1992.
  12. ^ Costas Courcoubetis, Mihalis Yannakakis, La complejidad de la verificación probabilística, Journal of the ACM, v.42 n.4, p.857-907, julio de 1995.
  13. ^ R. Alur, A. Itai, RP Kurshan, M. Yannakakis, Verificación de tiempos por aproximación sucesiva, Información y Computación, v.118 n.1, p.142-157, abril de 1995.
  14. ^ Groce, A., Peled, D. y Yannakakis, M. 2002. Comprobación del modelo adaptativo. En Actas de la 8ª Conferencia internacional sobre herramientas y algoritmos para la construcción y análisis de sistemas (8-12 de abril de 2002). J. Katoen y P. Stevens, Eds. Notas de la conferencia en Ciencias de la Computación, vol. 2280. Springer-Verlag, Londres, 357-370.
  15. ^ Rajeev Alur, Kousha Etessami, Mihalis Yannakakis, Realizabilidad y verificación de gráficos MSC, Informática teórica, v.331 n.1, p.97-114, 15 de febrero de 2005.
  16. ^ "Becarios AAAS elegidos" (PDF) . Avisos de la Sociedad Matemática Estadounidense .

Enlaces externos [ editar ]

  • Página de inicio en Columbia