| 2020 | RECOMB | PWAS: Proteome-Wide Association Study. | Nadav Brandes, Nathan Linial, Michal Linial |
| 2011 | RECOMB | Geometric Interpretation of Gene Expression by Sparse Reconstruction of Transcript Profiles. | Yosef Prat, Menachem Fromer, Michal Linial, Nathan Linial |
| 2005 | RECOMB | Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis. | Doron Lipson, Yonatan Aumann, Amir Ben-Dor, Nathan Linial, Zohar Yakhini |
| 2004 | FOCS | Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. | Yonatan Bilu, Nathan Linial |
| 2003 | STOC | On metric ramsey-type phenomena. | Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor |
| 2002 | ISMB | The metric space of proteins-comparative study of clustering algorithms. | Ori Sasson, Nathan Linial, Michal Linial |
| 2002 | STOC | Girth and euclidean distortion. | Nathan Linial, Avner Magen, Assaf Naor |
| 2001 | SODA | Random lifts of graphs. | Alon Amit, Nathan Linial, Jir Matousek, Eyal Rozenman |
| 1998 | ISMB | A Map of the Protein Space: An Automatic Hierarchical Classification of all Protein Sequences. | Golan Yona, Nathan Linial, Naftali Tishby, Michal Linial |
| 1998 | STOC | Trees and Euclidean Metrics. | Nathan Linial, Avner Magen, Michael E. Saks |
| 1998 | STOC | A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. | Nathan Linial, Alex Samorodnitsky, Avi Wigderson |
| 1996 | STOC | The Linear-Array Conjecture in Communication Complexity is False. | Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky |
| 1996 | STOC | Non-Expansive Hashing. | Nathan Linial, Ori Sasson |
| 1994 | FOCS | The geometry of graphs and some of its algorithmic applications | Nathan Linial, Eran London, Yuri Rabinovich |
| 1994 | SODA | Neighborhood Preserving Hashing and Approximate Queries. | Danny Dolev, Yuval Harari, Nathan Linial, Noam Nisan, Michal Parnas |
| 1993 | STOC | Fast perfection-information leader-election protocol with linear immunity. | Jason Cooper, Nathan Linial |
| 1993 | STOC | Efficient construction of a small hitting set for combinatorial rectangles in high dimension. | Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman |
| 1992 | STOC | Biased Random Walks | Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven J. Phillips |
| 1991 | FOCS | Fault-tolerant Computation in the Full Information Model (Extended Abstract) | Oded Goldreich, Shafi Goldwasser, Nathan Linial |
| 1991 | SODA | Decomposing Graphs into Regions of Small Diameter. | Nathan Linial, Michael E. Saks |
| 1990 | STOC | Approximate Inclusion-Exclusion | Nathan Linial, Noam Nisan |
| 1989 | FOCS | Constant Depth Circuits, Fourier Transform, and Learnability | Nathan Linial, Yishay Mansour, Noam Nisan |
| 1989 | FOCS | Graph Products and Chromatic Numbers | Nathan Linial, Umesh V. Vazirani |
| 1989 | STOC | On the Complexity of Radio Communication (Extended Abstract) | Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1989 | STOC | Compact Distributed Data Structures for Adaptive Routing (Extended Abstract) | Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1988 | COLT | Results on Learnability and the Vapnick-Chervonenkis Dimension. | Nathan Linial, Yishay Mansour, Ronald L. Rivest |
| 1988 | FOCS | The Influence of Variables on Boolean Functions (Extended Abstract) | Jeff Kahn, Gil Kalai, Nathan Linial |
| 1988 | FOCS | Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract) | Nathan Linial, Yishay Mansour, Ronald L. Rivest |
| 1987 | FOCS | Distributive Graph Algorithms-Global Solutions from Local Data | Nathan Linial |
| 1987 | STOC | An Optimal Online Algorithm for Metrical Task Systems | Allan Borodin, Nathan Linial, Michael E. Saks |
| 1987 | STOC | Imperfect Random Sources and Discrete Controlled Processes | David Lichtenstein, Nathan Linial, Michael E. Saks |
| 1986 | FOCS | A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications | Nathan Linial, Lszl Lovsz, Avi Wigderson |
| 1985 | FOCS | Multi-Layer Grid Embeddings | Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson |
| 1985 | FOCS | Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values | Michael Ben-Or, Nathan Linial |
| 1985 | STOC | Dual Integer Linear Programs and the Relationship between their Optima | Ron Aharoni, Paul Erds, Nathan Linial |
| 1983 | FOCS | Legal Coloring of Graphs | Nathan Linial |
| 1983 | FOCS | Information Bounds Are Good for Search Problems on Ordered Data Structures | Nathan Linial, Michael E. Saks |