Nati Linial

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."
• . This paper on competitive analysis of online algorithms 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 AC⁰, Linial and his co-authors show that these functions behave poorly as pseudorandom number generators, can be approximated well by polynomials, 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 spaces 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 graphs.