Nati Linial
Nati Linial, Nathan Linial ( born 1953 in Haifa) is an Israeli computer scientists and mathematicians.
Linial studied at the Technion and in 1978 received his doctorate in Micha Perles at the Hebrew University. As a post - graduate student he was at the University of California, Los Angeles. He is a professor of computer science at the Hebrew University.
He focuses on combinatorics, graph theory, theory of algorithms with application of methods from geometry and analysis on the analysis algorithms in molecular biology.
In 1992, he led by Allan Borodin and Michael E. Saks Metrical Task Systems (MTS ) for the analysis of online algorithms, and gave an optimal in many situations online algorithm to ..
In 1993, he exhibited with Yishay Mansour, Noam Nisan, and that functions of the class AC0 are ill-suited as a pseudo-random number generators are well approximated by polynomials and easily accessible to the machine learning.
By Eran London, and Yuri Rabinovich, he analyzed 1995 graph by geometric embedding in metric spaces in the lowest possible dimension and with the least possible distortion (which they developed efficient algorithms ) .. That they turned to the analysis of a number of algorithms, such as network flows ( multi commodity flow problem) and clustering of data, in the statistics.
Linial received in 2008 with Shlomo Hoory and Avi Wigderson the Levi L. Conant - Prize ( for expander graphs and their applications ) and the 2013 Dijkstra Prize ( for Locality in Distributed Graph Algorithms )
In 2002 he was invited speaker at the International Congress of Mathematicians (Finite metric spaces - combinatorics, geometry and algorithms ). He is a Fellow of the American Mathematical Society.
Writings
- Game - Theoretic Aspects of Computer Science, in Robert Aumann, S. Hart (Eds. ) Handbook of Game Theory with Economic Applications, Volume 2, Chapter 38, North Holland 1994, pp. 1340-1395
- M. Ben -Or Collective coin - flipping, Silvio Micali in Randomness and Computation, Academic Press 1989, pp. 91-115