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 computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
, 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; he, הַאוּנִיבֶרְסִיטָה הַעִבְרִית בִּירוּשָׁלַיִם) is a public research university based in Jerusalem, Israel. Co-founded by Albert Einstein and Dr. Chaim Weiz ...
, 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 St ...
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](_blank)
/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 task (project management), tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order ...
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 the representation of Function (mathematics), functions or signals as the Superposition principle, superposition of basic waves, and the study of and generalization of the notions of Fo ...
on functions in the complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
AC0 (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. Equiva ...
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 exa ...
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 p ...
, 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 settin ...
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 The Levi L. Conant Prize is a mathematics prize of the American Mathematical Society, which has been awarded since 2000 for outstanding expository papers published in the ''Bulletin of the American Mathematical Society'' or the ''Notices of the Amer ...
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, ...
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 applicati ...
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