El diploma en Ingeniería Eléctrica que Mihalis Yannakakis recibió de la Universidad Politécnica Nacional de Atenas en 1975 marcó el inicio de una larga carrera en la teoría de la complejidad computacional. Nacido en 1953 en Atenas, más tarde obtuvo un doctorado en Ciencias de la Computación en la Universidad de Princeton, influyendo posteriormente en la teoría de bases de datos, la verificación y la teoría de grafos algorítmica.
Fundamentos en la complejidad
Yannakakis pasó más de dos décadas en la investigación industrial, comenzando su mandato en los Laboratorios Bell en 1978. Allí se desempeñó como Director del Departamento de Investigación de Principios de Computación de 1991 a 2001. Durante este período, colaboró con Christos Papadimitriou en 1988 para definir las clases de complejidad Max-NP y Max-SNP, proporcionando una explicación rigurosa de las limitaciones observadas al aproximar problemas NP-hard como el problema del viajante y 3SAT. Su trabajo de 1993 con Carsten Lund aclaró aún más la dificultad inherente de calcular soluciones aproximadas para problemas de minimización como la coloración de grafos.
Innovaciones en bases de datos
Sus contribuciones a la teoría de bases de datos se centraron en la optimización del procesamiento de consultas mediante el estudio de esquemas acíclicos. Introdujo el algoritmo de Yannakakis para consultas conjuntivas acíclicas, demostrando que estas estructuras podían resolverse en tiempo polinómico. Más allá de la optimización de consultas, investigó las políticas de bloqueo, demostrando que la seguridad de las bases de datos podía mantenerse fuera de las restricciones rígidas del bloqueo en dos fases mediante la utilización de la estructura de hipergrafos de los datos y las restricciones de consistencia de transacciones para evitar interbloqueos.
Verificación y liderazgo académico
Tras su transición al ámbito académico, Yannakakis ocupó una cátedra en la Universidad de Stanford en 2002 antes de unirse a la Universidad de Columbia en 2004. Actualmente es profesor de Ciencias de la Computación Percy K. y Vida L. W. Hudson. Su investigación en verificación asistida por computadora estableció bases algorítmicas para probar la lógica temporal de tiempo lineal y los diagramas de secuencia de mensajes. También desarrolló la verificación de modelos adaptativos junto con Alex Groce y Doron Peled, un método que perfecciona los modelos de sistemas basándose en los resultados de la verificación.
Veinte preguntas, ocho minutos de reloj y un percentil medido frente a todos los que la han hecho. Sin registro.
Hacer la prueba de CI →Reconocimiento profesional
Yannakakis ha mantenido una presencia editorial significativa, habiendo sido editor en jefe del SIAM Journal on Computing entre 1998 y 2003. Su prestigio académico se refleja en sus membresías en la Academia Nacional de Ciencias, la Academia Nacional de Ingeniería, la Academia Estadounidense de Artes y Ciencias y la Academia Europaea. Sus premios incluyen el Premio Knuth de 2005 y el Premio de Teoría John von Neumann de 2023.
Datos rápidos
- Nacimiento: 1953, Atenas, Grecia - Doctorado: Universidad de Princeton, 1979 - Premio Knuth: 2005 - Premio de Teoría John von Neumann: 2023 - Miembro de la ACM: 1998 - Nacionalidad: Estados Unidos; Grecia - Idiomas: griego moderno
Preguntas frecuentes de los lectores
### ¿Qué es el algoritmo de Yannakakis?
Es un método utilizado para ejecutar consultas conjuntivas acíclicas en sistemas de bases de datos, permitiendo que se resuelvan en tiempo polinómico.
### ¿A qué instituciones ha estado afiliado Yannakakis?
Ha trabajado en Bell Laboratories, Avaya Laboratories, la Universidad de Stanford y la Universidad de Columbia.
.jpg)
