Nathan (Nati) Linial (born 1953 in

Haifa Haifa ( he, חֵיפָה ' ; ar, حَيْفَا ') is the third-largest city in Israel—after Jerusalem and Tel Aviv—with a population of in . The city of Haifa forms part of the Haifa metropolitan area, the third-most populous metropol ...

Israel Israel (; he, יִשְׂרָאֵל, ; ar, إِسْرَائِيل, ), officially the State of Israel ( he, מְדִינַת יִשְׂרָאֵל, label=none, translit=Medīnat Yīsrāʾēl; ), is a country in Western Asia. It is situated ...

) 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, and an

ISI highly cited researcher The Institute for Scientific Information (ISI) was an academic publishing service, founded by Eugene Garfield in Philadelphia in 1956. ISI offered scientometric and bibliographic database services. Its specialty was citation indexing and analysis, ...

. Linial did his undergraduate studies at the Technion, and received his PhD in 1978 from the Hebrew University under the supervision of Micha Perles. He was a postgraduate researcher at the

University of California, Los Angeles The University of California, Los Angeles (UCLA) is a public land-grant research university in Los Angeles, California. UCLA's academic roots were established in 1881 as a teachers college then known as the southern branch of the California S ...

before returning to the Hebrew University as a faculty member. In 2012 he became a fellow of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

. 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.

Selected publications

*. The paper won the 2013

Dijkstra Prize The Edsger W. Dijkstra Paper Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at lea ...

. 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."2013 Edsger W. Dijkstra Prize in Distributed Computing
/ref> *. This paper on competitive analysis of

online algorithm In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an o ...

s 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 A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are ...

problems, and develops an algorithm that in many situations can be shown to perform optimally. *. By performing harmonic analysis on functions in the

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...

AC⁰ (a class representing highly

parallelizable In mathematics, a differentiable manifold M of dimension ''n'' is called parallelizable if there exist smooth vector fields \ on the manifold, such that at every point p of M the tangent vectors \ provide a basis of the tangent space at p. Equi ...

computational problems), Linial and his co-authors show that these functions behave poorly as

pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...

s, can be approximated well by

polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...

s, and can be learned efficiently by

machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...

systems. *. Linial's most-cited paper according to

Google scholar Google Scholar is a freely accessible web search engine that indexes the full text or metadata of scholarly literature across an array of publishing formats and disciplines. Released in beta in November 2004, the Google Scholar index includes ...

, this paper explores connections between graph-theoretic problems such as the

multi-commodity flow problem The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. Definition Given a flow network \,G(V,E), where edge (u,v) \in E has capacity \,c(u,v). There are \,k comm ...

and low-distortion embeddings of

metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...

s into low-dimensional spaces such as those given by the

Johnson–Lindenstrauss lemma In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a ...

. *. In 2008 Linial and his co-authors won the Levi L. Conant Prize of the

for best mathematical exposition for this article, a survey on

expander graph In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applica ...

s..

References

{{DEFAULTSORT:Linial, Nathan Combinatorialists Theoretical computer scientists Technion – Israel Institute of Technology alumni Einstein Institute of Mathematics alumni Academic staff of the Hebrew University of Jerusalem Israeli computer scientists Israeli mathematicians Fellows of the American Mathematical Society 1953 births Living people Dijkstra Prize laureates