GetWiki

| last1 = Linial | first1 = Nati
| doi = 10.1137/0221015
| issue = 1
| journal = SIAM J. Comput.
| pages = 193–201
| title = Locality in Distributed Graph Algorithms
| volume = 21
| year = 1992| citeseerx = 10.1.1.471.6378
}}. 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."2013 Edsger W. Dijkstra Prize in Distributed Computing

| last1 = Borodin | first1 = Allan | author1-link = Allan Borodin
| last2 = Linial | first2 = Nathan
| last3 = Saks | first3 = Michael E. | author3-link = Michael Saks (mathematician)
| doi = 10.1145/146585.146588
| issue = 4
| journal = J. ACM
| pages = 745–763
| title = An optimal on-line algorithm for metrical task system
| volume = 39
| year = 1992| s2cid = 18783826 | doi-access = free
}}. 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.

| last1 = Linial | first1 = Nathan
| last2 = Mansour | first2 = Yishay
| last3 = Nisan | first3 = Noam | author3-link = Noam Nisan
| doi = 10.1145/174130.174138
| issue = 3
| journal = J. ACM
| pages = 607–620
| title = Constant depth circuits, Fourier transform, and learnability
| volume = 40
| year = 1993| s2cid = 16978276
| doi-access = free
}}. 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 generators, can be approximated well by polynomials, and can be learned efficiently by machine learning systems.

| last1 = Linial | first1 = Nathan
| last2 = London | first2 = Eran
| last3 = Rabinovich | first3 = Yuri
| doi = 10.1007/BF01200757
| issue = 2
| journal = Combinatorica
| pages = 215–245
| title = The geometry of graphs and some of its algorithmic applications
| volume = 15
| year = 1995| s2cid = 5071936
}}. 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.

| last1 = Hoory | first1 = Shlomo
| last2 = Linial | first2 = Nathan
| last3 = Wigderson | first3 = Avi | author3-link = Avi Wigderson
| doi = 10.1090/S0273-0979-06-01126-8
| mr = 2247919
| issue = 4
| journal = Bulletin of the American Mathematical Society
| pages = 439–561
| title = Expander graphs and their applications
| volume = 43
| year = 2006| doi-access = free
}}. 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.{{citation
| issue = 4
| journal = Notices of the American Mathematical Society
| pages = 491–493
| title = 2008 Conant Prize
| url =weblink
| volume = 55
| year = 2008}}.