Mihalis Yannakakis

La laurea in Ingegneria Elettrica che Mihalis Yannakakis ha conseguito presso l'Università Tecnica Nazionale di Atene nel 1975 ha segnato l'inizio di una lunga carriera nella teoria della complessità computazionale. Nato nel 1953 ad Atene, ha successivamente conseguito un dottorato in Informatica presso l'Università di Princeton, influenzando in seguito la teoria dei database, la verifica e la teoria dei grafi algoritmica.

Fondamenti nella complessità

Yannakakis ha trascorso oltre due decenni nella ricerca industriale, iniziando la sua attività presso i Bell Laboratories nel 1978. Ha ricoperto la carica di Direttore del Computing Principles Research Department dal 1991 al 2001. Durante questo periodo, ha collaborato con Christos Papadimitriou nel 1988 per definire le classi di complessità Max-NP e Max-SNP, fornendo una spiegazione rigorosa delle limitazioni osservate nell'approssimazione di problemi NP-hard come il problema del commesso viaggiatore e il 3SAT. Il suo lavoro del 1993 con Carsten Lund ha ulteriormente chiarito la difficoltà intrinseca di calcolare soluzioni approssimate per problemi di minimizzazione come la colorazione dei grafi.

Innovazioni nei database

I suoi contributi alla teoria dei database si sono concentrati sull'ottimizzazione dell'elaborazione delle interrogazioni attraverso lo studio di schemi aciclici. Ha introdotto l'algoritmo di Yannakakis per interrogazioni congiuntive acicliche, dimostrando che queste strutture potevano essere risolte in tempo polinomiale. Oltre all'ottimizzazione delle interrogazioni, ha studiato le politiche di blocco, dimostrando che la sicurezza dei database poteva essere mantenuta al di fuori dei rigidi vincoli del blocco a due fasi, utilizzando la struttura a ipergrafo dei dati e i vincoli di coerenza delle transazioni per prevenire i deadlock.

Verifica e leadership accademica

Passando al mondo accademico, Yannakakis ha ricoperto una cattedra presso la Stanford University nel 2002 prima di entrare alla Columbia University nel 2004. Attualmente è Percy K. and Vida L. W. Hudson Professor of Computer Science. La sua ricerca nella verifica assistita da computer ha stabilito le basi algoritmiche per il test della logica temporale a tempo lineare e dei Message Sequence Charts. Ha inoltre sviluppato l'Adaptive Model Checking insieme ad Alex Groce e Doron Peled, un metodo che affina i modelli di sistema sulla base dei risultati della verifica.

Riconoscimenti professionali

Yannakakis ha mantenuto una significativa presenza editoriale, avendo servito come caporedattore del SIAM Journal on Computing tra il 1998 e il 2003. La sua posizione accademica si riflette nelle sue affiliazioni alla National Academy of Sciences, alla National Academy of Engineering, all'American Academy of Arts and Sciences e all'Academia Europaea. I suoi premi includono il Knuth Prize del 2005 e il John von Neumann Theory Prize del 2023.

Informazioni rapide

- Nato: 1953, Atene, Grecia - Dottorato: Università di Princeton, 1979 - Knuth Prize: 2005 - John von Neumann Theory Prize: 2023 - ACM Fellow: 1998 - Cittadinanza: Stati Uniti; Grecia - Lingue: Greco moderno

Domande frequenti dei lettori

### Cos'è l'algoritmo di Yannakakis?

È un metodo utilizzato per eseguire interrogazioni congiuntive acicliche nei sistemi di database, consentendo loro di essere risolte in tempo polinomiale.

### Con quali istituzioni è stato affiliato Yannakakis?

Ha lavorato presso i Bell Laboratories, gli Avaya Laboratories, la Stanford University e la Columbia University.