Nati Linial
Encyclopedia
Nathan Linial (born 1953 in Haifa
, Israel
) is an Israel
i 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.
Linial did his undergraduate studies at the Technion, and received his Ph.D. in 1978 from the Hebrew University under the supervision of Micha Perles. He was a postgraduate researcher at the University of California, Los Angeles
before returning to the Hebrew University as a faculty member.
of online algorithm
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
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
AC0
(a class representing highly parallelizable
computational problems), Linial and his co-authors show that these functions behave poorly as pseudorandom number generator
s, can be approximated well by polynomial
s, and can be learned efficiently by machine learning
systems.. 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 space
s into low-dimensional spaces such as those given by the Johnson–Lindenstrauss lemma
.. 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 graph
s.
Haifa
Haifa is the largest city in northern Israel, and the third-largest city in the country, with a population of over 268,000. Another 300,000 people live in towns directly adjacent to the city including the cities of the Krayot, as well as, Tirat Carmel, Daliyat al-Karmel and Nesher...
, Israel
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
) is an Israel
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
i mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the Hebrew University of Jerusalem
Hebrew University of Jerusalem
The Hebrew University of Jerusalem ; ; abbreviated HUJI) is Israel's second-oldest university, after the Technion – Israel Institute of Technology. The Hebrew University has three campuses in Jerusalem and one in Rehovot. The world's largest Jewish studies library is located on its Edmond J...
, and an ISI highly cited researcher.
Linial did his undergraduate studies at the Technion, and received his Ph.D. in 1978 from the Hebrew University under the supervision of Micha Perles. He was a postgraduate researcher at the University of California, Los Angeles
University of California, Los Angeles
The University of California, Los Angeles is a public research university located in the Westwood neighborhood of Los Angeles, California, USA. It was founded in 1919 as the "Southern Branch" of the University of California and is the second oldest of the ten campuses...
before returning to the Hebrew University as a faculty member.
Selected publications
. This paper on competitive analysisCompetitive analysis (online algorithm)
Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...
of online algorithm
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 offline algorithm is given the whole problem data from...
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
Job Shop Scheduling
Job shop scheduling is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:...
problems, and develops an algorithm that in many situations can be shown to perform optimally.. By performing harmonic analysis
Harmonic analysis
Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
on functions in the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
AC0
AC0
AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and OR gates....
(a class representing highly parallelizable
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
computational problems), Linial and his co-authors show that these functions behave poorly as pseudorandom number generator
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
s, can be approximated well by polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s, and can be learned efficiently by machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
systems.. Linial's most-cited paper according to Google scholar
Google Scholar
Google Scholar is a freely accessible web search engine that indexes the full text of scholarly literature across an array of publishing formats and disciplines. Released in beta in November 2004, the Google Scholar index includes most peer-reviewed online journals of Europe and America's largest...
, this paper explores connections between graph-theoretic problems such as the multi-commodity flow problem
Multi-commodity flow problem
The multi-commodity flow problem is a network flow problem with multiple commodities flowing through the network, with different source and sink nodes.-Definition:Given a flow network \,G, where edge \in E has capacity \,c...
and low-distortion embeddings of metric space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s into low-dimensional spaces such as those given by the Johnson–Lindenstrauss lemma
Johnson–Lindenstrauss lemma
In mathematics, the Johnson–Lindenstrauss lemma is a result concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such...
.. In 2008 Linial and his co-authors won the Levi L. Conant Prize of the American Mathematical Society
American Mathematical Society
The American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...
for best mathematical exposition for this article, a survey on expander graph
Expander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
s.