Nathan (Nati) Linial (Haifa, 1953)^[1] é um matemático e cientista da computação israelense, professor da Rachel and Selim Benin School of Computer Science and Engineering da Universidade Hebraica de Jerusalém,^[2] e um dos pesquisadores mais citados do ISI.^[3]

Linial estudou no Technion, e obteve um doutorado em 1978 na Universidade Hebraica de Jerusalém, orientado por Micha Perles.^[1][4] Foi pesquisador de pós-graduação na Universidade da Califórnia em Los Angeles antes de retornar para a Universidade Hebraica de Jerusalém como professor.^[1]

Em 2012 foi eleito fellow da American Mathematical Society.^[5]

Publicações selecionadas

• Linial, Nati (1992), «Locality in Distributed Graph Algorithms», SIAM J. Comput., 21 (1): 193–201, doi:10.1137/0221015 . O artigo ganhou o Prêmio Dijkstra de 2013. In the words of the prize committee: "This paper has had a major impact on distributed message-passing algorithms. It focused a spotlight on the notion of locality in distributed computation and raised interesting questions concerning the locality level of various distributed problems, in terms of their time complexity on different classes of networks. Towards that goal, in this paper, Linial developed a model particularly suitable for studying locality, which ignores message sizes, asynchrony and failures. This clean model allowed researchers to isolate the effects of locality and study the roles of distances and neighborhoods, as graph theoretic notions, and their interrelations with algorithmic and complexity-theoretic problems in distributed computing."^[6]
• Borodin, Allan; Linial, Nathan; Saks, Michael E. (1992), «An optimal on-line algorithm for metrical task system», J. ACM, 39 (4): 745–763, doi:10.1145/146585.146588 . This paper on competitive analysis of online algorithms studies metrical task systems, a very general model of tasks where decisions on how to service a sequence of requests must be made without knowledge of future requests. It introduces the metrical task system model, describes how to use it to model various scheduling problems, and develops an algorithm that in many situations can be shown to perform optimally.
• Linial, Nathan; Mansour, Yishay; Nisan, Noam (1993), «Constant depth circuits, Fourier transform, and learnability», J. ACM, 40 (3): 607–620, doi:10.1145/174130.174138 . By performing harmonic analysis on functions in the complexity class AC⁰ (a class representing highly parallelizable computational problems), Linial and his co-authors show that these functions behave poorly as pseudorandom number generators, can be approximated well by polynomials, and can be learned efficiently by machine learning systems.
• Linial, Nathan; London, Eran; Rabinovich, Yuri (1995), «The geometry of graphs and some of its algorithmic applications», Combinatorica, 15 (2): 215–245, doi:10.1007/BF01200757 . Linial's most-cited paper according to Google Scholar, this paper explores connections between graph-theoretic problems such as the multi-commodity flow problem and low-distortion embeddings of metric spaces into low-dimensional spaces such as those given by the Johnson–Lindenstrauss lemma.
• Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), «Expander graphs and their applications», Bulletin of the American Mathematical Society, 43 (4): 439–561, MR 2247919, doi:10.1090/S0273-0979-06-01126-8 . In 2008 Linial and his co-authors won the Prêmio Levi L. Conant of the American Mathematical Society for best mathematical exposition for this article, a survey on expander graphs.^[1]

Referências