Nathan (Nati) Linial (; born 1953 in

Haifa Haifa ( ; , ; ) is the List of cities in Israel, 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 metropolitan area i ...

, Israel) is an Israeli mathematician and

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the

Hebrew University of Jerusalem The Hebrew University of Jerusalem (HUJI; ) is an Israeli public university, public research university based in Jerusalem. Co-founded by Albert Einstein and Chaim Weizmann in July 1918, the public university officially opened on 1 April 1925. ...

, 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 university, public Land-grant university, land-grant research university in Los Angeles, California, United States. Its academic roots were established in 1881 as a normal school the ...

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 Noam Nisan (; born June 20, 1961) is an Israeli computer scientist and professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory. Biography Ni ...

Selected publications

*. 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."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 of ...

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

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

harmonic analysis Harmonic analysis is a branch of mathematics concerned with investigating the connections between a function and its representation in frequency. The frequency representation is found by using the Fourier transform for functions on unbounded do ...

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

AC⁰ (a class representing highly

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

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 number generation, random n ...

s, can be approximated well by

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

s, and can be learned efficiently by

machine learning Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...

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 Academic publishing, scholarly literature across an array of publishing formats and disciplines. Released in Beta release, beta in November 2004, th ...

, this paper explores connections between graph-theoretic problems such as the multi-commodity flow problem and low-distortion embeddings of

metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...

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

. *. In 2008 Linial and his co-authors won the

Levi L. Conant Prize The Levi L. Conant Prize is a mathematics prize of the American Mathematical Society, which has been awarded since 2001 for outstanding expository papers published in the ''Bulletin of the American Mathematical Society'' or the ''Notices of the Ame ...

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

s..

References

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