Nati Linial - Nati Linial

Nathan (Nati) Linial (narozen 1953 v Haifa, Izrael )[1] je izraelský matematik a počítačový vědec, profesor na Rachel and Selim Benin School of Computer Science and Engineering na Hebrejská univerzita v Jeruzalémě,[2] a ISI vysoce citovaný výzkumník.[3]

Linial absolvoval vysokoškolské studium na Technion, a doktorát získal v roce 1978 na Hebrejské univerzitě pod vedením Michae Perlese.[1][4] Byl postgraduálním výzkumníkem na University of California, Los Angeles před návratem na Hebrejskou univerzitu jako člen fakulty.[1]

V roce 2012 se stal členem Americká matematická společnost.[5] V roce 2019 získal cenu FOCS Test of Time za článek „Konstantní hloubkové obvody, Fourierova transformace a učitelnost", spoluautorem s Yishay Mansour a Noam Nisan. [6]

Vybrané publikace

  • 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. Práce zvítězila v roce 2013 Dijkstra cena. Slovy cenové komise: „Tento příspěvek měl zásadní dopad na distribuované algoritmy pro předávání zpráv. Zaměřil se na pozornost na pojem lokality v distribuovaném výpočtu a nastolil zajímavé otázky týkající se úrovně lokality různých distribuovaných problémů, pokud jde o své časové složitosti na různých třídách sítí. Směrem k tomuto cíli vyvinul Linial model zvláště vhodný pro studium lokality, který ignoruje velikosti zpráv, asynchronii a selhání. Tento čistý model umožnil výzkumníkům izolovat účinky lokality a studovat role vzdáleností a sousedství jako teoretické pojmy grafů a jejich vzájemné vztahy s algoritmickými a komplexně teoretickými problémy v distribuovaných výpočtech. “[7]
  • Borodin, Allane; Linial, Nathan; Saks, Michael E. (1992), „Optimální on-line algoritmus pro metrický systém úloh“, J. ACM, 39 (4): 745–763, doi:10.1145/146585.146588. Tento dokument o konkurenční analýza z online algoritmy studie systémy metrických úloh, velmi obecný model úkolů, kde rozhodnutí o tom, jak obsloužit sled požadavků, musí být učiněny bez znalosti budoucích požadavků. Představuje model metrického systému úloh, popisuje, jak jej použít k modelování různých plánování problémy a vyvíjí algoritmus, u kterého lze v mnoha situacích prokázat optimální výkon.
  • Linial, Nathan; Mansour, Yishay; Nisan, Noame (1993), "Obvody s konstantní hloubkou, Fourierova transformace a učitelnost", J. ACM, 40 (3): 607–620, doi:10.1145/174130.174138. Provedením harmonická analýza o funkcích v třída složitosti AC0 (třída vysoce reprezentující paralelizovatelný výpočtové problémy), Linial a jeho spoluautoři ukazují, že tyto funkce se chovají špatně generátory pseudonáhodných čísel, lze dobře aproximovat pomocí polynomy, a lze se je efektivně naučit pomocí strojové učení systémy.
  • Linial, Nathan; Londýn, Eran; Rabinovich, Yuri (1995), „Geometrie grafů a některé jejich algoritmické aplikace“, Combinatorica, 15 (2): 215–245, doi:10.1007 / BF01200757. Nejcitovanější článek Liniala podle Google učenec, tento článek zkoumá souvislosti mezi graficko-teoretickými problémy, jako je problém multikomoditního toku a vložení s nízkým zkreslením metrické prostory do nízkodimenzionálních prostorů, jako jsou ty, které poskytuje Johnson – Lindenstraussovo lemma.
  • Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), „Expander graphs and their applications“, Bulletin of the American Mathematical Society, 43 (4): 439–561, doi:10.1090 / S0273-0979-06-01126-8, PAN  2247919. V roce 2008 Linial a jeho spoluautoři vyhráli Cena Levi L. Conant z Americká matematická společnost pro nejlepší matematickou expozici pro tento článek průzkum na expandérové ​​grafy.[1]

Reference

  1. ^ A b C d „Conant Prize 2008“ (PDF), Oznámení Americké matematické společnosti, 55 (4): 491–493, 2008.
  2. ^ Domovská stránka Liniala na Hebrejské univerzitě, vyvoláno 08.09.2010.
  3. ^ Web znalostí ISI Archivováno 19. května 2007 v Wayback Machine, vyvoláno 08.09.2010.
  4. ^ Nati Linial na Matematický genealogický projekt
  5. ^ Seznam členů Americké matematické společnosti, vyvoláno 2013-01-27.
  6. ^ „Vítězové ocenění FOCS 2019“.
  7. ^ Cena Edsgera W. Dijkstra 2013 za distribuované výpočty