Nati Linial

Datei:Prof. Nathan (Nati) Linial - Professor of Computer Science - Hebrew University.jpg

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.<ref>Mathematics Genealogy Project.</ref> 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.<ref>Borodin, Linial, Saks "An optimal on-line algorithm for metrical task system", J. ACM, Band 39, 1992, S. 745–763.</ref>

1993 zeigte er mit Yishay Mansour und Noam Nisan<ref>Linial, Mansour, Nisam Constant depth circuits, Fourier transform, and learnability, J. ACM, Band 40, 1993, S. 607–620.</ref> 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).<ref>Linial, London, Rabinovich "The geometry of graphs and some of its algorithmic applications", Combinatorica, Band 15, 1995, S. 215–245.</ref> 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)<ref>Hoory, Linial, Wigderson, Bulletin of the AMS, Bd. 43, 2006, Nr. 4, S. 439–561.</ref> und 2013 den Dijkstra-Preis (für Locality in Distributed Graph Algorithms).<ref>Linial, SIAM Journal on Computing, Band 21, 1992, S. 193–201.</ref>

2002 war er Gastredner auf dem Internationalen Mathematikerkongress (Finite metric spaces - combinatorics, geometry and algorithms). Er ist Fellow der American Mathematical Society.

Schriften (Auswahl)[Bearbeiten]

Außer den in den Fußnoten aufgeführten Schriften.

Game-Theoretic Aspects of Computer Science, in Robert Aumann, S. Hart (Herausgeber) Handbook of Game Theory with Economic Applications, Band 2, Kapitel 38, North Holland 1994, S. 1340–1395
mit M. Ben-Or Collective coin-flipping, in Silvio Micali Randomness and Computation, Academic Press 1989, S. 91–115
mit Yuval Peled: On the phase transition in random simplicial complexes, Annals of Mathematics, Band 184, 2016, S. 745–773