Nati Linial

from Wikipedia, the free encyclopedia

Nati Linial , also Nathan Linial (* 1953 in Haifa ) is an Israeli computer scientist and mathematician.

Linial studied at the Technion and received his doctorate in 1978 from Micha Perles at the Hebrew University . He was a post-doctoral student at the University of California, Los Angeles . He is a professor of computer science at the Hebrew University.

He deals with combinatorics , graph theory , theory of algorithms with the application of methods from geometry and analysis to their analysis, algorithms in molecular biology.

In 1992, together with Allan Borodin and Michael E. Saks, he introduced Metrical Task Systems (MTS) for the analysis of online algorithms and specified an online algorithm that is optimal in many situations.

In 1993, together with Yishay Mansour and Noam Nisan , he showed that class AC0 functions are poorly suited as pseudo-random number generators , can be approximated well by polynomials, and are easily accessible to machine learning.

With Eran London and Yuri Rabinovich, he analyzed graphs in 1995 by embedding them geometrically in metric spaces in the lowest possible dimension and with the lowest possible distortion (for which they developed efficient algorithms). They applied this to the analysis of a number of algorithms such as network flows (multi commodity flow problem) and clustering of data in statistics.

Linial received the Levi L. Conant Prize (for Expander graphs and their applications ) in 2008 with Shlomo Hoory and Avi Wigderson and the Dijkstra Prize in 2013 (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 .

Fonts (selection)

Except for the fonts listed in the footnotes.

  • Game-Theoretic Aspects of Computer Science , in Robert Aumann , S. Hart (editor) Handbook of Game Theory with Economic Applications , Volume 2, Chapter 38, North Holland 1994, pp. 1340-1395
  • with M. Ben-Or Collective coin-flipping , in Silvio Micali Randomness and Computation , Academic Press 1989, pp. 91-115
  • with Yuval Peled: On the phase transition in random simplicial complexes , Annals of Mathematics, Volume 184, 2016, pp. 745-773

Web links

Individual evidence

  1. ^ Mathematics Genealogy Project
  2. ↑ Borodin, Linial, Saks "An optimal on-line algorithm for metrical task system", J. ACM, Volume 39, 1992, pp. 745-763
  3. ↑ Linial, Mansour, Nisam Constant depth circuits, Fourier transform, and learnability , J. ACM, Vol. 40, 1993, pp. 607-620
  4. ↑ Linial, London, Rabinovich "The geometry of graphs and some of its algorithmic applications", Combinatorica, Vol. 15, 1995, pp. 215-245
  5. ↑ Hoory, Linial, Wigderson, Bulletin of the AMS, Vol. 43, 2006, No. 4, pp. 439-561
  6. ↑ Linial, SIAM Journal on Computing, Volume 21, 1992, pp. 193-201
personal data
SURNAME Linial, Nati
ALTERNATIVE NAMES Linial, Nathan
BRIEF DESCRIPTION Israeli computer scientist
DATE OF BIRTH 1953
PLACE OF BIRTH Haifa