Nati Linial

Nathan (Nati) Linial (ur. 1953 w Hajfie , Izrael ) jest izraelskim matematykiem i informatykiem , profesorem w Rachel i Selim Benin School of Computer Science and Engineering na Uniwersytecie Hebrajskim w Jerozolimie oraz wysoko cytowanym badaczem ISI .

Linial ukończył studia licencjackie na Technion , a stopień doktora uzyskał w 1978 roku na Uniwersytecie Hebrajskim pod kierunkiem Michy Perlesa. Był badaczem podyplomowym na Uniwersytecie Kalifornijskim w Los Angeles, zanim wrócił na Uniwersytet Hebrajski jako członek wydziału.

W 2012 roku został członkiem Amerykańskiego Towarzystwa Matematycznego . W 2019 roku zdobył nagrodę FOCS Test of Time Award za artykuł „ Obwody o stałej głębokości, transformacja Fouriera i zdolność uczenia się ”, którego współautorem są Yishay Mansour i Noam Nisan.

Wybrane publikacje

•   Linial, Nati (1992), „Lokalizacja w algorytmach grafów rozproszonych”, SIAM J. Comput. , 21 (1): 193–201, CiteSeerX 10.1.1.471.6378 , doi : 10.1137/0221015 . Artykuł zdobył w 2013 roku nagrodę Dijkstra . Jak stwierdził komitet nagrody: „Ten artykuł wywarł duży wpływ na algorytmy rozproszonego przesyłania wiadomości. Skupił się na pojęciu lokalności w obliczeniach rozproszonych i poruszył interesujące pytania dotyczące poziomu lokalności różnych rozproszonych problemów, pod względem ich złożoności czasowej w różnych klasach sieci. W tym celu Linial opracował w tym artykule model szczególnie odpowiedni do badania lokalizacji, który ignoruje rozmiary wiadomości, asynchronię i awarie. Ten czysty model pozwolił naukowcom wyizolować skutki lokalizacji i zbadać role odległości i sąsiedztw jako pojęć teorii grafów oraz ich wzajemne powiązania z problemami algorytmicznymi i teoretycznymi złożoności w obliczeniach rozproszonych”.
•   Borodin, Allan ; Linial, Nathan; Saks, Michael E. (1992), „Optymalny algorytm on-line dla systemu zadań metrycznych”, J. ACM , 39 (4): 745–763, doi : 10.1145/146585.146588 , S2CID 18783826 . Ten artykuł na temat konkurencyjnej analizy algorytmów online bada systemy zadań metrycznych , bardzo ogólny model zadań, w którym decyzje o sposobie obsługi sekwencji żądań muszą być podejmowane bez wiedzy o przyszłych żądaniach. Wprowadza metryczny model systemu zadań, opisuje, jak używać go do modelowania różnych związanych z planowaniem i rozwija algorytm, który w wielu sytuacjach można wykazać, że działa optymalnie.
•   Linial, Nathan; Mansour, Yishay; Nisan, Noam (1993), „Obwody o stałej głębokości, transformata Fouriera i zdolność uczenia się”, J. ACM , 40 (3): 607–620, doi : 10.1145/174130.174138 , S2CID 16978276 . Przeprowadzając analizę harmoniczną funkcji w klasie złożoności AC ⁰ (klasie reprezentującej wysoce równoległe problemy obliczeniowe), Linial i jego współautorzy pokazują, że funkcje te zachowują się słabo jako generatory liczb pseudolosowych , można dobrze aproksymować wielomianami i skutecznie uczyć się za pomocą systemów uczenia maszynowego .
•   Linial, Nathan; Londyn, Eran; Rabinovich, Yuri (1995), „Geometria grafów i niektóre z jej zastosowań algorytmicznych”, Combinatorica , 15 (2): 215–245, doi : 10.1007 / BF01200757 , S2CID 5071936 . Według badacza Google , najczęściej cytowany artykuł Liniala , ten artykuł bada powiązania między problemami teorii grafów, takimi jak problem przepływu wielu towarów, a osadzeniem przestrzeni metrycznych o niskim zniekształceniu w przestrzeniach niskowymiarowych, takich jak te podane przez Lemat Johnsona-Lindenstraussa .
•   Hoory, Szlomo; Linial, Nathan; Wigderson, Avi (2006), „Wykresy ekspanderów i ich zastosowania”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 43 (4): 439–561, doi : 10.1090 / S0273-0979-06-01126-8 , MR 2247919 . W 2008 roku Linial i jego współautorzy zdobyli nagrodę im. Leviego L. Conanta przyznawaną przez Amerykańskie Towarzystwo Matematyczne za najlepszą ekspozycję matematyczną za ten artykuł, ankietę dotyczącą grafów ekspanderów .