Nati Linial - Nati Linial
Nathan (Nati) Linial (urodzony 1953 roku w Hajfie , Izrael ) to izraelski matematyk i informatyk , profesor w Rachel i Selim Benin Szkoły Informatyki i Inżynierii na Uniwersytecie Hebrajskim w Jerozolimie , i ISI bardzo cytowany badacz .
Linial ukończył studia licencjackie na Technion , a doktorat uzyskał w 1978 roku na Uniwersytecie Hebrajskim pod kierunkiem Michy Perlesa. Był badaczem podyplomowym na Uniwersytecie Kalifornijskim w Los Angeles, zanim powrócił na Uniwersytet Hebrajski jako członek wydziału.
W 2012 został stypendystą 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 uczenie się ”, którego współautorem jest Yishay Mansour i Noam Nisan.
Wybrane publikacje
- Linial, Nati (1992), "Locality in Distributed Graph Algorithms", SIAM J. Comput. , 21 (1): 193-201, CiteSeerX 10.1.1.471.6378 , doi : 10.1137/0221015. Gazeta zdobyła nagrodę Dijkstry 2013 . Według słów kapituły nagrody: „Ten artykuł wywarł duży wpływ na rozproszone algorytmy przekazywania komunikatów. Skupił się na pojęciu lokalności w obliczeniach rozproszonych i postawił interesujące pytania dotyczące poziomu lokalności różnych problemów rozproszonych, 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, asynchroniczność i awarie. Ten czysty model pozwolił naukowcom wyodrębnić efekty lokalizacji i role odległości i sąsiedztwa, jako pojęcia teorii grafów, oraz ich wzajemne powiązania z problemami algorytmicznymi i teorii złożoności w obliczeniach rozproszonych."
- Borodin, Allan ; Linial, Nathan; Saks, Michael E. (1992), „Optymalny algorytm on-line dla metrycznego systemu zadań”, J. ACM , 39 (4): 745-763, doi : 10.1145/146585.146588 , S2CID 18783826. Ten papier na analizy konkurencyjnej o algorytm online studia metryczne systemów zadaniowych , bardzo ogólny model zadań, w których decyzje dotyczące sposobu obsługi sekwencję wniosków muszą być wykonane bez wiedzy przyszłych wniosków. Wprowadza metryczny model systemu zadań, opisuje, jak go używać do modelowania różnych problemów związanych z harmonogramowaniem 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, transformacja Fouriera i uczenie się", J. ACM , 40 (3): 607-620, doi : 10.1145/174130.174138 , S2CID 16978276. Wykonując analizę harmoniczną funkcji w klasie złożoności AC 0 (klasa reprezentująca wysoce zrównoleglone problemy obliczeniowe), Linial i jego współautorzy pokazują, że funkcje te słabo zachowują się jak generatory liczb pseudolosowych , mogą być dobrze aproksymowane przez wielomiany i można się ich nauczyć wydajnie przez systemy uczenia maszynowego .
- Linial, Nathan; Londyn, Eran; Rabinovich, Yuri (1995), „Geometria wykresów i niektóre z jego zastosowań algorytmicznych”, Combinatorica , 15 (2): 215-245, doi : 10.1007/BF01200757 , S2CID 5071936. Najczęściej cytowany artykuł Linial według badacza Google , ten artykuł bada powiązania między problemami teorii grafów, takimi jak problem przepływu wielu towarów i osadzenia przestrzeni metrycznych o niskim poziomie zniekształceń 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 Linial i jego współautorzy wygrał Levi L. CONANT Nagrodę z American Mathematical Society dla najlepszego matematycznego ekspozycji na potrzeby tego artykułu, badania dotyczącego ekspandera wykresach .