Nathan (Nati) Linial (born 1953 in Haifa, Israel)^[1] is an Israeli mathematician and computer scientist, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the Hebrew University of Jerusalem,^[2] and an ISI highly cited researcher.^[3]

Linial did his undergraduate studies at the Technion, and received his PhD in 1978 from the Hebrew University under the supervision of Micha Perles.^[1][4] He was a postgraduate researcher at the University of California, Los Angeles before returning to the Hebrew University as a faculty member.^[1]

In 2012 he became a fellow of the American Mathematical Society.^[5] In 2019 he won the FOCS Test of Time Award for the paper "Constant Depth Circuits, Fourier Transform, and Learnability", co-authored with Yishay Mansour and Noam Nisan. ^[6]

Selected publications

• 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. The paper won the 2013 Dijkstra Prize. 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."^[7]
• 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, S2CID 18783826. 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, S2CID 16978276. 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, S2CID 5071936. 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, doi:10.1090/S0273-0979-06-01126-8, MR 2247919. In 2008 Linial and his co-authors won the Levi L. Conant Prize of the American Mathematical Society for best mathematical exposition for this article, a survey on expander graphs.^[1]