Nati Linial

Nati Linial, auch Nathan Linial (* 1953 in Haifa) ist ein israelischer Informatiker und Mathematiker. Linial studierte am Technion und wurde 1978 bei Micha Perles an der Hebräischen Universität promoviert. Als Post-Doktorand war er an der University of California, Los Angeles. Er ist Professor für Informatik an der Hebräischen Universität. Er befasst sich mit Kombinatorik, Graphentheorie, Theorie der Algorithmen mit Anwendung von Methoden aus Geometrie und Analysis auf deren Analyse, Algorithmen in der Molekularbiologie. 1992 führte er mit Allan Borodin und Michael E. Saks Metrical Task Systems (MTS) zur Analyse von Online-Algorithmen ein und gaben einen in vielen Situationen optimalen Online-Algorithmus an. 1993 zeigte er mit Yishay Mansour und Noam Nisan dass Funktionen der Klasse AC0 schlecht als Pseudozufallszahlengeneratoren geeignet sind, gut durch Polynome approximierbar sind und gut dem Maschinenlernen zugänglich. Mit Eran London und Yuri Rabinovich analysierte er 1995 Graphen durch geometrische Einbettung in metrische Räume in möglichst niedriger Dimension und mit möglichst geringer Verzerrung (wozu sie effiziente Algorithmen entwickelten). Das wandten sie auf die Analyse einer Reihe von Algorithmen an wie Netzwerkflüsse (multi commodity flow problem) und Clustering von Daten in der Statistik. Linial erhielt 2008 mit Shlomo Hoory und Avi Wigderson den Levi-L.-Conant-Preis (für Expander graphs and their applications) und 2013 den Dijkstra-Preis (für Locality in Distributed Graph Algorithms). 2002 war er Gastredner auf dem Internationalen Mathematikerkongress (Finite metric spaces - combinatorics, geometry and algorithms). Er ist Fellow der American Mathematical Society.