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.^[1] 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.^[2]

1993 zeigte er mit Yishay Mansour und Noam Nisan^[3] 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).^[4] 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)^[5] und 2013 den Dijkstra-Preis (für Locality in Distributed Graph Algorithms).^[6]

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

Außer den in den Fussnoten 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

• Homepage

1. ↑ Mathematics Genealogy Project.
2. ↑ Borodin, Linial, Saks "An optimal on-line algorithm for metrical task system", J. ACM, Band 39, 1992, S. 745–763.
3. ↑ Linial, Mansour, Nisam Constant depth circuits, Fourier transform, and learnability, J. ACM, Band 40, 1993, S. 607–620.
4. ↑ Linial, London, Rabinovich "The geometry of graphs and some of its algorithmic applications", Combinatorica, Band 15, 1995, S. 215–245.
5. ↑ Hoory, Linial, Wigderson, Bulletin of the AMS, Bd. 43, 2006, Nr. 4, S. 439–561.
6. ↑ Linial, SIAM Journal on Computing, Band 21, 1992, S. 193–201.