Mihalis Yannakakis

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar

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

Educación y carrera

Yannakakis nació en Atenas, Grecia, en 1953 y cursó sus primeros estudios en la escuela secundaria Varvakeio. Se graduó de la Universidad Técnica Nacional de Atenas en 1975 con un diploma en Ingeniería Eléctrica y posteriormente obtuvo su doctorado en Ciencias de la Computación en la Universidad de Princeton en 1979. Su tesis se tituló «La complejidad de los problemas de subgrafos máximos».En 1978 se incorporó a Bell Laboratories y fue Director del Departamento de Investigación de Principios de Computación desde 1991 hasta 2001, cuando dejó Bell Laboratories y se incorporó a Avaya Laboratories. Allí fue Director del Departamento de Investigación de Principios de Computación hasta 2002.En 2002 se incorporó a la Universidad de Stanford, donde fue profesor de informática, y la abandonó en 2003 para incorporarse a la Universidad de Columbia en 2004, donde actualmente ocupa la cátedra Percy K. y Vida L. W. Hudson de informática.De 1992 a 2003, Yannakakis formó parte del consejo editorial de la revista SIAM Journal on Computing y fue editor jefe entre 1998 y 2003. También fue miembro del consejo editorial de la revista ACM de 1986 a 2000. También ha sido miembro de consejos editoriales como la revista Journal of Computer and System Sciences, la revista Journal of Combinatorial Optimization y la revista Journal of Complexity. También ha formado parte de comités de congresos y ha presidido diversas conferencias, como el Simposio ACM sobre Principios de Sistemas de Bases de Datos y el Simposio IEEE sobre Fundamentos de la Informática.

A junio de 2020, sus publicaciones habían sido citadas cerca de 35.000 veces y tenía un índice h de 93.

Research

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 dificultad de aproximación. En el Simposio Anual de la ACM sobre Teoría de la Computación de 1988, Yannakakis y Christos Papadimitriou introdujeron las definiciones de las clases de complejidad Max-NP y Max-SNP. Max-NP y Max-SNP (una subclase de Max-NP) contienen varios problemas de optimización interesantes, y Yannakakis y Papadimitriou demostraron que estos problemas tienen cierto error acotado. Estos hallazgos permitieron explicar la falta de progreso observado en la comunidad investigadora sobre la aproximabilidad de varios problemas de optimización, incluyendo 3SAT, el problema de los conjuntos independientes y el problema del viajante.

Yannakakis y Carsten Lund presentaron varios hallazgos sobre la dificultad de calcular aproximaciones en el Simposio Anual de la ACM sobre Teoría de la Computación de 1993. Estos hallazgos demostraron la dificultad de calcular eficientemente soluciones aproximadas para diversos problemas de minimización, como la coloración de grafos y el cubrimiento de conjuntos. Dado el improbable escenario de que problemas NP-difíciles, como la coloración de grafos y el cubrimiento de conjuntos, se resolvieran óptimamente en tiempo polinomial, se habían realizado numerosos intentos para desarrollar soluciones de aproximación eficientes; los resultados obtenidos por Yannakakis y Carsten demostraron la improbabilidad de lograr esta tarea.En el área de la teoría de bases de datos, sus contribuciones incluyen el inicio del estudio de esquemas de bases de datos acíclicos, consultas conjuntivas acíclicas y bloqueos no bifásicos. Los esquemas de bases 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 rige la unión de las tablas de la base de datos) y un conjunto de dependencias funcionales. Varios investigadores, incluido Yannakakis, destacaron la utilidad de estos esquemas al demostrar sus numerosas propiedades útiles: por ejemplo, la capacidad de resolver muchos problemas basados en esquemas acíclicos en tiempo polinomial, mientras que el problema podría haber sido fácilmente NP-completo para otros esquemas.Con respecto al bloqueo no bifásico, Yannakakis demostró cómo el conocimiento sobre la estructura de una base de datos y las formas de las diversas transacciones que se ejecutan en ella puede utilizarse para determinar si una política de bloqueo específica es segura. Las políticas de bloqueo bifásico (2PL) comúnmente utilizadas constan de dos etapas: bloquear y desbloquear entidades, respectivamente. Para evitarlo, es necesario imponer cierta estructura a las entidades de una base de datos. Los resultados de Yannakakis muestran cómo, al elegir un hipergrafo similar a la estructura de restricción de consistencia de una base de datos, una política de bloqueo que visita las entidades a lo largo de las rutas de este hipergrafo será segura. Dicha política no necesita ser bifásica, y estas políticas pueden clasificarse según la conectividad del hipergrafo mencionado, siendo las políticas 2PL solo un ejemplo particular. Yannakakis continuó demostrando que, para la clase natural de políticas de bloqueo seguro (políticas L), la ausencia de interbloqueos se determina únicamente por el orden en que las transacciones acceden a las entidades, y de esto derivó condiciones simples que garantizarían la ausencia de interbloqueos para una política L.También ha contribuido al área de verificación y pruebas asistidas por computadora, donde sentó las rigurosas bases algorítmicas y de teoría de la complejidad del campo. Algunas de sus contribuciones incluyen el diseño de algoritmos eficientes en memoria para la verificación de propiedades temporales de programas de estados finitos, la determinación de la complejidad al probar si los programas cumplen sus especificaciones expresadas en lógica temporal de tiempo lineal y la verificación de que un modelo con restricciones temporales satisface una propiedad temporal dada. Junto con Alex Groce y Doron Peled, introdujo la Comprobación Adaptativa de Modelos, demostrando que cuando existen inconsistencias entre un sistema y el modelo correspondiente, los resultados de la verificación pueden utilizarse para mejorar el modelo. También ha contribuido a la investigación sobre Gráficos de Secuencia de Mensajes (MSC), donde se demostró que la realizabilidad débil es indecidible para grafos MSC acotados y que la realizabilidad segura está en EXPSPACE, junto con otros resultados interesantes relacionados con la verificación de grafos MSC.

Premios y reconocimiento

Yannakakis es miembro de la Academia Nacional de Ingeniería y de la Academia Nacional de Ciencias. Recibió el séptimo premio Knuth por sus contribuciones a la informática teórica. También recibió el Premio al Miembro Distinguido del Personal Técnico de Bell Labs y el Premio de Oro del Presidente de Bell Labs, en 1985 y 2000, respectivamente. Es miembro de la ACM y de Bell Laboratories. Fue elegido miembro de la Academia Estadounidense de las Artes y las Ciencias (AAAS) en 2020.

Referencias

  1. ^ a b c d e f g Columbia Universidad: CV: Mihalis Yannakakis (aprobado el 12 de noviembre de 2009)
  2. ^ 2005 Knuth Prize Mihalis Yannakakis, ACM, 1 May 2006
  3. ^ a b Knuth Prize
  4. ^ The Mathematics Genealogy Project – Mihalis Yannakakis (accessed 9 December 2009)
  5. ^ "Google Scholar Record of M. Yannakakis".
  6. ^ Christos Papadimitriou, Mihalis Yannakakis, Optimización, aproximación y clases de complejidad, Proceedings of the twenty annual ACM symposium on Theory of computing, pp. 229–234, 2–4 May 1988.
  7. ^ Carsten Lund, Mihalis Yannakakis, Sobre la dureza de los problemas de minimización aproximados, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 286–293, 16–18 May 1993.
  8. ^ Catriel Beeri, Ronald Fagin, David Maier, Alberto Mendelzon, Jeffrey Ullman, Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirtyth annual ACM symposium on Theory of computing, pp. 355–362, 11–13 May 1981.
  9. ^ Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM, v.30 n.3, pp. 479–513, July 1983.
  10. ^ Mihalis Yannakakis, A Theory of Safe Locking Policies in Database Systems, Journal of the ACM, v.29 n.3, pp. 718–740, July 1982.
  11. ^ Mihalis Yannakakis, Freedom from deadlocks of safe locking policies, SIAM J. on Computing 11 (1982), 391-408.
  12. ^ C. Courcoubetis, M. Vardi, P. Wolper, M. Yannakakis, Memory-efficient algoritmos for the verification of temporal properties, Formal Methods in System Design, v.1 n.2-3, pp. 275–288, Oct. 1992.
  13. ^ Costas Courcoubetis, Mihalis Yannakakis, The complex of probabilistic verification, Journal of the ACM, v.42 n.4, pp. 857–907, July 1995.
  14. ^ R. Alur, A. Itai, R. P. Kurshan, M. Yannakakis, Timing verification by successive aproximation, Information and Computation, v.118 n.1, pp. 142–157, April 1995.
  15. ^ Groce, A., Peled, D., and Yannakakis, M. 2002. Adaptive Model Checking. En Proceedings of the 8th international Conference on Tools and Algorithms For the Construction and Analysis of Systems (8–12 de abril de 2002). J. Katoen y P. Stevens, Eds. Conference Notes in Computer Science, vol. 2280. Springer-Verlag, Londres, 357-370.
  16. ^ Rajeev Alur, Kousha Etessami, Mihalis Yannakakis, Realizability and verification of MSC graphs, Theoretical Computer Science, v.331 n.1, pp. 97–114, 15 February 2005.
  17. ^ "AAS Fellows Elected" (PDF). Avisos de la American Mathematical Society.
  • Página principal en Columbia
Más resultados...
Te puede interesar
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save
cancelcheck_circle