Nati Linial : Home page

Nathan (Nati) Linial

    School of Computer Science and Engineering
    The Hebrew University of Jerusalem
    Jerusalem 91904
    Israel

    email: nati@cs.huji.ac.il
    phone: +972-2-5494548
                                                                              fax: +972-2-5494548

I am a Professor at the School of Computer Science and Engineering, in the Hebrew University of Jerusalem.

Research Interests

Combinatorics; The Theory of Algorithms; Applications of Geometry and Analysis to the above fields; Computational Molecular Biology.

My record at:

I am an AMS Fellow, MathSciNet, DBLP, Google Scholar. .

Editorial

Israel Journal of Mathematics, Editorial Board (Chief Editor 2013-2017).
Random Structures and Algorithms, Editorial Board.
Combinatorica, Editorial Board.

Textbook in discrete math (in Hebrew)

Table of content
Introduction
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Appendix
Index

Course materials

Harmonic Analysis and Combinatorial Applications, Taught at University of Washington, Winter 2005.
Algorithms. In Hebrew, material for our second year course. Still in somewhat messy condition. The title says what's in the file.

Popular scientific material (mostly in Hebrew)

Expanders, (in Hebrew) Annual retreat of the Center for Rationality, March 2019.
On the limitations of human knowledge, (in Hebrew). Israel Academy of Sciences, February 2019. The slides.
Euler and the magic of numbers, (Powerpoint presentation, In Hebrew, A popular lecture at Beit Ariela, Tel Aviv in their series "The great Scientists" December 2008).
Randomness - Friend or foe?, (Powerpoint presentation, In Hebrew, HUJI's MADU'A lectures May 2007).
Ten milestones in the history of mathematics, (With Gil Kalai, In Hebrew, Galileo December 2006).

Web sites

ProtoNet

EVEREST

Past students (including some theses)

Recent Talks

Simplicial Complexes - Combinatorial and Probabailistic Challenges, RS&A Conference, Gniezno, Poland, August 2022,
Geodesic Geometry on Graphs, EPC Webinar, December 2020.
Hypertrees, HUJI Math Colloquium June 2020, I gave a similar talk also at Uri Feige 60 Fest, January 2020.
Challenges of high-dimensional combinatorics, Laszlo Lovasz 70th birthday conference, Budapest July 2018. I managed to present about 2/3 of the slides.
Random high-dimensional combinatorial objects,, Simons Instiute, Berkeley, April 2017.
Hypertrees,, Rutgers, Mike Saks 60th Birthday, January 2017.
What are high-dimensional expanders ?, Simons Institute, Berkeley, February 2017.
Transitions and phase transitions, Avi60 October '16.
High-dimensional permutations, (a recording), and slides from Nogafest January '16, and from the Jirka Matousek Memorial Meeting, July 2016.
A glimpse of high-dimensional combinatorics, ITW May '15.
Random Simplial Complexes, Lecture at the 18th MIDRASHA Mathematicae, "In and around combiantorics".
Simplicial complexes are more than a trick for distributed computing lower bounds, Disc conference, October '13. My Dijkstra Prize presentation.
The local geometry of graphs, or, how to ``read" big graphs. Lecture, slides, and a more technical presentation. Simons Institute, UC Berkeley, September '13.
What are high-dimensional permutations? How many are there?, IPAM reunion meeting in combinatorics, Lake Arrowhead, June '11.
No Justified complains: A Bottleneck-based fair resource sharing, Innovations in Algorithmic Game Theory, Jerusalem, May '11.
Going up in dimension: Probabilistic and combinatorial aspects of simplicial complexes, Random Structures and Algorithms, Poznan, August '09.
Random Lifts of Graphs, 27th Brazilian Math Colloquium, Rio de Janeiro, July '09.
What is high-dimensional combinatorics?, Random-Approx, August '08.
Ramanujan graphs, lifts and word maps, Israel CS Theory day, March '08, and ``Building Bridges'', a conference in honor of L. Lovasz, August '08.
On eigenvalues and eigenvectors of graphs, ETH, Zurich, May '08.
Some problems and results in the geometry of graphs, This file combines talks given in EPFL Lausanne Feb. 2007, and ICMS Edinburgh, April 2007.
Expander Graphs - Are There Any Mysteries Left?, Talk given April 2006, Diskrete Mathematik, Berlin.
Lifts of Graphs, Summer '05.

Publications

Mathematics and Theoretical Computer Science

Computational Molecular Biology

Survey Articles and Chapters in Books

Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson, Bull. AMS, 43(2006) 439--561. This paper was awarded the 2008 Conant Prize.

Finite Metric Spaces - Combinatorics, Geometry and Algorithms, N. Linial, Proceedings of the International Congress of Mathematicians III, 573--586 Beijing, 2002.

Game-Theoretic Aspects of Computer Science, N. Linial, in " Handbook of Game Theory with Economic Applications", vol. II, chapter 38,
(R. J. Aumann and S. Hart eds.) North Holland, 1994, pp. 1340-1395.
Collective coin flipping, M. Ben-Or and N. Linial, in "Randomness and Computation" (S. Micali ed.) Academic Press, New York, 1989, pp. 91-115.
Collective coin flipping and other models of imperfect randomness, M. Ben-Or, N. Linial and M. Saks, in Colloq. Math Soc. Janos Bolyai no. 52, Combinatorics Eger 1987 pp. 75-112.

Some Recent Manuscripts

The Rank-Ramsey problem and the log-rank conjecture, Gal Beniamini, Nati Linial and Adi Shraibman.
An Elementary Proof of the First LP Bound on the Rate of Binary Codes, Nati Linial and Elyassaf Loyfer.
Linear Programming Hierarchies in Coding Theory: Dual Solutions, Nati Linial and Elyassaf Loyfer.
A note on Fermat's Last Theorem for n=4, Matan Eliashar and Nati Linial.
Bounds on unique-neighbor codes, Nati Linial and Idan Orzech.
Published Papers

How balanced can permutations be? Gal Beniamini, Nir Lavee, and Nati Linial. Combinatorica, accepted for publication.
On the Löwner-John Ellipsoids of the Metric Polytope, Raziel Gartsman and Nati Linial. Discrete and Computational Geometry, accepted for publication.
The structure of metrizable graphs, Maria Chudnovsky, Daniel Cizma and Nati Linial. Discrete and Computational Geometry, accepted for publication.
An approach to the girth problem in cubic graphs, Aya Bernstine and Nati Linial. Journal of Graph Theory, accepted for publication.
On the Connectivity and Diameter of Geodetic Graphs, Asaf Etgar and Nati Linial. European Journal of Combinatorics, accepted for publication.
New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes, Nati Linial and Elyassaf Loyfer, IEEE Transactions on Information Theory, 69(2023), 2886-2899 .
On the local structure of oriented graphs -- a case study in flag algebras, Shoni Gilboa, Roman Glebov, Dan Hefetz, Nati Linial, Avraham Morgenstern, Electronic J. of Combinatorics, Vol. 29 #3 (2022).
Irreducible nonmetrizable path systems in graphs, Daniel Cizma and Nati Linial, Journal of Graph Theory, 102(2023), 5-14.
Larger corner-free sets from better NOF exactly-N protocols, Nati Linial and Adi Shraibman. Discrete Analysis 2021:19, 9 pp.
In search of Hyperpaths, Amir Dahari and Nati Linial. Discrete and Computational Geometry, 69, 399–421 (2023).
Geodesic Geometry on Graphs, Daniel Cizma and Nati Linial. Discrete and Computational Geometry, 68 (2022) 298-347.
Functional Evolutionary Modeling Exposes Overlooked Protein-Coding Genes Involved in Cancer. Nadav Brandes, Nati Linial and Michal Linial, ISBRA 2020. Lecture Notes in Computer Science, vol 12304. Springer, Cham. 119-126. https://doi.org/10.1007/978-3-030-57821-3_11,
Expanding cancer predisposition genes with ultra-rare cancer-exclusive human variations, Roni Rasnic, Nati Linial and Michal Linial, Scientific Reports volume 10, Article number: 13462 (2020).
PWAS: Proteome-wide Association Study - Linking Genes and Phenotypes by Functional Variation in Genes, Supplementary material, Nadav Brandes, Nati Linial and Michal Linial, Genome Biology, Genome Biol 21, 173 (2020).
A randomized construction of high girth regular graphs, Nati Linial and Michael Simkin. Random Structures and Algorithms, 58(2) 345-369 (2021).
Efficient, local and symmetric Markov chain that generate one-factorizations, Maya Dotan, Nati Linial, and Yuval Peled. Acta Math. Hungarica, 161, 557–568(2020).
Asymptotically almost every 2r-regular graph has an internal partition, Sria Louis and Nati Linial. Graphs and Combinatorics, 36 (2020), 41-50.
Quantifying gene selection in cancer through protein functional alteration bias, Nadav Brandes, Nati Linial and Michal Linial, Nucleic Acid Research, 47 (2019) 6642--6655.
Expander Graphs, both Local and Global, Michael Chapman, Nati Linial and Yuval Peled, FOCS 2019, 158-170, and Combinatorica, 40(4) 473-509 (2020).
A cell-based probabilistic approach unveils the concerted action of miRNAs, Shelly Mahlab-Aviv, Nati Linial and Michal Linial, PLOS Computational Biology, https://doi.org/10.1371/journal.pcbi.1007204.
On the weight distribution of random binary linear codes, Nati Linial and Jonathan Mosheiff, Random Strutures and Algorithms, 56(1): 5-36 (2020).
Universal knot diagrams, Chaim Even-Zohar, Joel Hass, Nati Linial and Tahl Nowik, Journal of Knot Theory and its Ramifications, 28 (2019), no. 7, 1950031, 30 pp.
The communication complexity of high-dimensional permutations, Nati Linial, Toni Pitassi and Adi Shraibman, ITCS 2019, 54:1-54:20.
The distribution of knots in the Petaluma model, Chaim Even-Zohar, Joel Hass, Nati Linial and Tahl Nowik. Algebraic and Geometric Topology 18 (2018), 3647--3668.
Enumeration and randomized constructions of hypertrees, Nati Linial and Yuval Peled, Discrete and Computational Geometry, 55 (2019), 677-695.
Extremal problems on shadows and hypercuts in simplicial complexes, Nati Linial, Ilan Newman, Yuval Peled, and Yuri Rabinovich, Israel J. Math, 229(2019) 133--163.
Enhancing identification of cancer types via lowly expressed microRNAs, Roni Rasnic, Nathan Linial and Michal Linial. Nucleic Acids Research, (2017) 45(9) 5048-5060.
Random Simplicial complexes - Around the phase transition, Nati Linial and Yuval Peled, A Journey Through Discrete Mathematics, A tribute to Jiri Matousek, 543--570 (2017).
Monotone subsequences in high-dimensional permutations, Nati Linial and Michael Simkin. Combninatorics, Probability and Computing, 27(1): 69-83 (2018).
On the rigidity of sparse random graphs, Nati Linial and Jonathan Mosheiff, J. Graph Theory, 85(2017), 466--480.
Invariants of random knots and links, Chaim Even-Zohar, Joel Hass, Nati Linial and Tahl Nowik, Discrete and Computational Geometry, 56(2016), 274-314.
Discrepancy of high-dimensional permutations, Nati Linial and Zur Luria, Discrete Analysis, 2016:11, 8pp.
On the phase transition in random simplicial complexes, Nati Linial and Yuval Peled, Annals of Math., 184(2016) 745--773.
Internal partitions of regular graphs, Amir Ban and Nati Linial. J. Graph Theory, 83(2016), 5-18.
On the number of 4-cycles in a tournament, Avraham Morgenstern and Nati Linial. J. Graph Theory, 83 (2016) 266--276.
The threshold for d-collapsibility in random complexes, Lior Aronshtam and Nati Linial, Random Structures and Algorithms, 48 (2016), 260-269. An error was discovered in this paper, but is now fixed.
On the local profiles of trees, Sebastien Bubeck and Nati Linial. J. Graph Theory, 81 (2016) 109--119.
The complexity of learning halfspaces using generalized linear methods, Amit Daniely, Nati Linial, and Shai Shalev-Shwartz, COLT 2014, 244-286.
Triply existentially complete triangle-free graphs, Nati Linial and Chaim Even-Zohar. J. Graph Theory, 78 (2015) 26--35.
A Note on the Inducibility of 4-Vertex Graphs, Nati Linial and Chaim Even-Zohar, Graphs and Combinatorics, 31(2015) 1367-1380.
From average case complexity to improper learning complexity, Amit Daniely, Nati Linial, and Shai Shalev-Shwartz, STOC 2014, 441-448.
Graphs with few 3-cliques and 3-anticliques are 3-universal, Nati Linial and Avraham Morgenstern. J. Graph Theory, 78 (2015), 229--238.
Entropy-driven partitioning of the hierarchical protein space, Nadav Rappoport, Amos Stern, Nathan Linial, Michal Linial, Bioinformatics 30(17) (2014) 624--630.
On regular hypergraphs of high girth, David Ellis and Nati Linial, Electronic J. of Combinatorics, Volume 21, Issue 1 (2014), paper 54.
On high-dimensional acyclic tournaments, Nati Linial and Avraham Morgenstern, Discrete and Computational Geometry: Volume 50, Issue 4 (2013), Page 1085-1100.
More data speeds up training time in learning halfspaces over sparse vectors, Amit Daniely, Nati Linial, and Shai Shalev-Shwartz, NIPS 2013, 145-153.
On the densities of cliques and independent sets in graphs, Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, and Benny Sudakov. Combinatorica, 32(2016), 493-512.
On the 3-local profiles of graphs, Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, and Benny Sudakov, Journal of Graph Theory, 76, (2014), 236--248.
On the vertices of the d-dimensional Birkhoff polytope, Nati Linial and Zur Luria, Discrete and Computational Geometry, 51 (2014), 161-170.
ProtoNet: charting the expanding universe of protein sequences, Rappoport N, Linial N, Linial M. Nature Biotechnology 2013 Apr;31(4):290-2.
An upper bound on the number of high-dimensional permutations, Nati Linial and Zur Luria, Combinatorica, 34(2014), 471-486.
On the practically interesting instances of MAXCUT, Yonatan Bilu , Amit Daniely, N. Linial, and M. Saks, STACS 2013, 526-537.
Collapsibility and vanishing of top homology in random simplicial complexes Lior Aronshtam, Nati Linial, Thomasz Luczak and Roy Meshulam, Discrete and Computational Geometry, 49 (2013), 317-334.
When does the top homology of a random simplicial complex vanish?, Lior Aronshtam and Nati Linial, Random Structures and Algorithms, 46 (2015) 26--35.
ProtoNet 6.0: Organizing 10 million protein sequences in a compact hierarchical family tree, Nadav Rappoport, Solange Karsenty, Amos Stein, Nathan Linial, and Michal Linial. Nucleic Acids Res. 2012 January; 40(D1): D313-D320.
Upper bounds on the number of Steiner triple systems and 1-factorizations, Nati Linial and Zur Luria. Random Structures and Algorithms, 43 (2013), 399 - 406.
Strong convergence in posets Amir Ban and Nati Linial, J. Combinatorial Theory ser. A, 119 (2012) 1299--1301.
No justified complaints: On fair sharing of multiple resources, Danny Dolev, Dror Feitelson, Joe Halpern, R. Kupferman and N. Linial, ITCS 2012, 68--75.
Musical Chairs, Yehuda Afek, Yakov Babichenko, Uri Feige, Eli Gafni, Nati Linial, and Benny Sudakov, SIAM J. Discrete Math., 2014(28), 1578--1600. An earlier (and quite different) version: Oblivious collaboration, DISC 2011, 489--504.
Generative probabilistic models for protein-protein interaction networks - The biclique perspective, Regev Schweiger, Michal Linial, and Nati Linial, Bioinformatics, 2011(27), 142--148.
On the Lipschitz constant of the RSK correspondence, Nayantara Bhatnagar and N. Linial. J. Combinatorial Theory ser. A, 2012 (119) 63-82.
Strategy and dynamics of reputation systems, Amir Ban and Nati Linial, TARK 2011, 91-100.
Recovering key biological constituents through sparse representation of gene expression, Yosef Prat, Menachem Fromer, N. Linial, and Michal Linial. Bioinformatics, 2011 (27) 655-661.
Tight products and graph expansion, Amit Daniely and N. Linial. J. Graph Theory, (2012) 69, 426--440.
The expected genus of a random chord diagram, N. Linial, and T. Nowik. Discrete and Computational Geometry, 2011(45) 161-180.
Codon usage is associated with the evolutionary age of genes in metazoan genomes, Yosef Prat , Menachem Fromer , N. Linial, and M. Linial, BMC Evolotionary Biology, 9(1) 285, 2009.
Are stable instances easy? Yonatan Bilu and N. Linial, Innovations in Computer Science, ICS 2010, Beijing, China, 332 - 341. Combinatorics, Probability and Computing, (2012) 21, 643--660.
Sum complexes - a new family of hypertrees, N. Linial, R. Meshulam, and M. Rosenthal. Discrete and Computational Geometry, 2010(44) 622-636.
Eigenvectors of random graphs: Nodal domains, Y. Dekel, J. R. Lee and N. Linial, Random Structures and Algorithms, 2011(39) 39-58.
Word maps and spectra of random graph lifts, N. Linial and D. Puder, Random Structures and Algorithms, 2010(37) 100--135.
Learning Complexity vs. Communication Complexity, N. Linial and A. Shraibman, Combninatorics, Probability and Computing, 2009(18) 227--245.
Graph coloring with no large monochromatics components, N. Linial and J. Matousek, O. Sheffet, and G. Tardos, Combninatorics, Probability and Computing, 2008(17) 577--589.
Lower Bounds in Communication Complexity Based on Factorization Norms, N. Linial and A. Shraibman, Random Structures and Algorithms, 34 (2009) 368--394.
EVEREST: A collection of evolutionary conserved protein domains, E. Portugaly, N. Linial, and M. Linial, Nucleic Acid Research, 2007, Vol. 35, Database issue D241-D246.
EVEREST: Automatically determined domain families in all protein sequences, E. Portugaly, A. Harel, N. Linial, and M. Linial, BMC-Bioinformatics (2006) 7:277.
Complexity measures of sign matrices, N. Linial, S. Mendelson, G. Schechtman and A. Shraibman, Combinatorica, 27(2007) 439-463.
The non-crossing graph, N. Linial, M. Saks and D. Statter. Electronic Journal of Combinatorics, vol. 13(1), 2006.
How neighborly can a centraly symmetric polytope be?, N. Linial, and I. Novik, Discrete and Computational Geometry, 36(2006) 273-281.
Efficient calculations of interval scores for DNA copy number data analysis, D. Lipson, Y. Aumann, A. Ben-Dor, N. Linial, and Z. Yakhini. Jour. Comp. Bio., 13 (2006) 215-228.
On the expansion rate of Margulis expanders, N. Linial, and E. London. Jour. Comb. Th. ser. B, 96 (2006), 436-442. Later remark on this paper.
A counterexample to a conjecture of Lovasz on the χ-coloring complex, Shlomo Hoory and N. Linial, Jour. Comb. Th. ser. B, 95(2005) 346 - 349.
Monotone Maps, Sphericity and Bounded Second Eigenvalue., Yonatan Bilu and N. Linial, Jour. Comb. Th. ser. B, 95(2005) 283-299.
Minors in lifts of graphs, Yotam Drier, and N. Linial, Random Structures and Algorithms, 29(2006), 208-225.
Some Low Distortion Metric Ramsey Problems, Y. Bartal, N. Linial, M. Mendel, and A. Naor. Discrete and Computational Geometry, 33(2005) 27-45.
Lifts, discrepancy and nearly optimal spectral gaps, Yonatan Bilu and N. Linial, Combinatorica, 26(2006) 495--519.
ProtoNet4.0: A Hierarchical classification of one million protein sequences, Noam Kaplan, Ori Sasson, Uri Inbar, Moriah Friedlich, Menachem Fromer, Hillel Fleischer, Elon Portugaly, Nathan Linial, and Michal Linial, Nucleic Acids Research, 33(2005) D216-D218.
Essential covers of the cube by hyperplanes, N. Linial and Jaikumar Radhakrishnan, Jour. Comb. Th. ser. A, 109(2005) 331 -- 338.
Limitations to Frechet Embedding of Metric Spaces, Y. Bartal, N. Linial, M. Mendel, and A. Naor, Israel J. Math., 151 (2006), 111--124.
On Metric Ramsey-Type Dichotomies, Y. Bartal, N. Linial, M. Mendel, and A. Naor, Jour. London Math. Soc., 71(2005) 289--303.
Approximate protein structural alignment in polynomial time, R. Kolodny and N. Linial, PNAS, 101(2004) ,12201-12206.
Homological connectivity of random 2-dimensional complexes, N. Linial, and R. Meshulam, Combinatorica, 26(2006) 475--487.
On Metric Ramsey-Type Phenomena, Y. Bartal, N. Linial, M. Mendel, and A. Naor, Annals of Mathematics 162 (2005) 643 - 709.
The metric space of proteins-comparative study of clustering algorithms., Sasson O, Linial N, Linial M, Bioinformatics, 18, S14-21.
ProtoNet: hierarchical classification of the protein space, Sasson O, Vaaknin A, Fleischer H, Portugaly E, Bilu Y, Linial N, Linial M, Nucleic Acids Res. 31, 348-352.
Low Dimensional Embeddings of Ultrametrics, Y. Bartal, N. Linial, M. Mendel, and A. Naor, Europ. J. Combin., 25(2004) 87-92.
Neighborhood preserving hashing and approximate queries, D. Dolev, Y. Harari, N. Linial, N. Nisan and M. Parnas, Siam Jour. Disc. Math. 15(2002), 73-85.
Metric Embeddings - Beyond one-dimensional distortion, R. Krauthgamer, N. Linial and A. Magen , Discrete and Computational Geometry, 31(2004) 339 - 356.
The one-round Voronoi game, Ottfried Cheong, S. Har-Peled, N. Linial and J. Matousek, Discrete and Computational Geometry, 31;125-138(2004).
Coloring of the d-regular infinite tree, N. Linial and S. Hoory, Jour. Comb. Th. ser. B, 91(2), 161-167, 2004.
On the Euclidean distortion of complete binary trees, N. Linial and M. Saks, Discrete and Computational Geometry, 29;19-21(2003).
A Continuous Analogue of the Girth Problem, A. Amit, S. Hoory and N. Linial, Jour. Comb. Th. ser. B, 84(2002) 340 - 363.
Random Lifts of Graphs II: Edge Expansion, A. Amit and N. Linial, Combinatorics Probability and Computing, 15(2006) 317-332.
Random Lifts of Graphs III: Independence and Chromatic Number, A. Amit, N. Linial and J. Matousek, Random Structures and Algorithms, 20(2002) 1-22.
Random Lifts of Graphs: Perfect Matchings, N. Linial, and E. Rozenman, Combinatorica, 25(2005) 407 - 424.
Girth and Euclidean distortion, N. Linial, A. Magen, and A. Naor, GAFA, 12(2002) 380--394.
The Moore bound for irregular graphs, N. Alon, S. Hoory and N. Linial, Graphs and Combinatorics, 18 (2002), 53--57.
The Linear-Array Conjecture in Communication Complexity is False, E. Kushilevitz, N. Linial and R. Ostrovski, Combinatorica, 19 (1999), no. 2, 241--254.
On the hardness of approximating the chromatic number, S. Khanna, N. Linial and S. Safra, Combinatorica, 20 (2000), no. 3, 393--415.
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, N. Linial, A. Samorodnitsky and A. Wigderson, Combinatorica, 20 (2000) 531-544.
Random Graph Coverings I: General Theory and Connectivity, A. Amit and N. Linial, Combinatorica, 22(2002) 1- 18.
An extremal problem on degree sequences of graphs, N. Linial and E. Rozenman, Graphs Combin. 18 (2002), no. 3, 573--582.
Random Lifts of Graphs, A. Amit, N. Linial, J. Matousek, and E. Rozenman, SODA 2001, 883--894.
ProtoMap: Automatic classification of protein sequences and hierarchy of protein families, G. Yona, N. Linial and M. Linial, Nucl. Acid Res. 28 (2000) 49-55.
Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders, N. Linial and A. Magen, J. Combinatorial Theory ser. B, 79 (2000) 157-171.
Automatic classification of protein sequences, a hierarchy of protein families, and local maps of the protein space, G. Yona, N. Linial and M. Linial, Proteins: Structure, Function, and Genetics. 37 (1999) 360-378.
On the design and analysis of protein folding potentials, D. Tobi, G. Shafran, N. Linial and R. Elber, PROTEINS: Structure Function and Genetics, 40 (2000) 71-85.
A note on the influence of ε-biased random source, A. Ben Dor, A. Karlin, N. Linial and Yu. Rabinovich, J. Comp. Sys. Sci., 58(1999) 174-176.
Competitive Optimal Online Leasing, R. El Yaniv, R. Kaniel and N. Linial, Algorithmica, 25(1999) 116-140.
Linear codes and character sums, N. Linial and A. Samorodnitsky, Combinatorica 22 (2002), no. 4, 497--522.
Non-expansive Hashing, N.Linial and O. Sasson, Combinatorica 18 (1998) 121-132.
Low distortion Euclidean embedding of trees, N. Linial, A. Magen and M. Saks, Israel J. Math., 106(1998) 339-348.
Inclusion-exclusion : exact and approximate, J. Kahn, N. Linial and A. Samorodnitsky, Combinatorica, 16(1996) 465 - 477.
Fault-tolerant computation in the full information model, O. Goldreich, S. Goldwasser and N. Linial, SIAM J. Comp., 27(1998) 506-544.
Global self organization of all known protein sequences reveals inherent biological signatures, M. Linial, N. Linial, N. Tishby and G. Yona, J. Mol. Biol., 268(1997) 539 - 556.
Efficient construction of small hitting set for combinatorial rectangles in high dimension, N. Linial, M. Luby, M. Saks and D. Zuckerman, Combinatorica, 17(1997) 215 - 234.
On the trace of incompatible vectors, R. Aharoni, N. Linial, and R. Meshulam, Cong. Numer. 113(1996) 15-18.
Central points for sets in Rⁿ (or, the chocolate ice cream problem), S. Hoory and N. Linial, Disc. Comp. Geom, 15(1996) 467 - 479.
On the potential of molecular computing, M. Linial and N. Linial, Letter to Science, 268 (1995), 481.
The geometry of graphs and some of its algorithmic applications, N. Linial, E. London and Yu. Rabinovich, Combinatorica, 15(1995) 215 - 245.
Witness sets for families of binary vectors (Note), E. Kushilevitz, N. Linial, Yu. Rabinovich and M. Saks, Jour. Combin. Theory ser. A, 73(1996) 376 - 380.
On the distance distribution of codes, G. Kalai and N. Linial, IEEE Trans. Inf. Th., 41(1995) 1467 - 1472.
Fast perfect-information leader election protocol with linear immunity, J. Cooper and N. Linial, Combinatorica, 15(1995) 319 - 332.
Biased random walks, Y. Azar, A. Broder, A. Karlin, N. Linial and S. Phillips, Combinatorica, 16(1996) 1-18.
Local-global phenomena in graphs, N. Linial, Combinatorics Probability and Computing, 2(1993) 491 - 503.
Low diameter graph decompositions, N. Linial and M. Saks, Combinatorica, 13(1993) 441 - 454.
Notes on convex body chasing, J. Friedman and N. Linial, Discrete and Computational Geometry, 9(1993) 293 - 321.
Local and global clique numbers, N. Linial and Y. Rabinovitch, Jour. Combin. Theory ser. B, 61(1994) 5 - 15.
On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels, Y. Birk, N. Linial and R. Meshulam, IEEE Infor. Th., 39, 1993, 186-191.
Single round simulation for radio networks, N. Alon, A. Bar-Noy, N. Linial and D. Peleg, Journal of Algorithms, 13(1992) 188 - 210.
Constant-depth circuits, Fourier transform and learnability, N. Linial Y. Mansour and N. Nisan, Jour. Assoc. Comput. Mach., 40 (1993) 607 - 620. FOCS Test of time award.
A geometric parallel search problem related to group testing, (Note) Z. Fueredi and N. Linial, Journal of Combinatorial Mathematics and Combinatorial Computing,12 (1992) 3--6.
Spectral properties of threshold functions, C. Gotsman and N. Linial, Combinatorica, 14(1994) 35 - 50.
The influence of large coalitions, M. Ajtai and N. Linial, Combinatorica, 13(1993) 129 - 145.
Group connectivity of graphs - A nonhomogeneous analogue of nowhere-zero flow properties , F. Jaeger, N. Linial, C. Payan and M. Tarsi, Jour. Comb. Th. ser. B, 56(1992) 165 - 182.
The influence of variables in product spaces, J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson and N. Linial, Israel Jour. Math., 77(1992) 55-64.
The equivalence of two problems on the cube, (Note) C. Gotsman and N. Linial, Jour. Combin. Theory ser. A., 61(1992) 142 -146.
Additive bases of vector spaces over prime fields, N. Alon, N. Linial and R. Meshulam, Journal of Combinatorial Theory ser. A, 57(1991) 203-210.
Locality in distributed graph algorithms, N. Linial, SIAM Journal on Computing, 21(1992) 193-201. This paper was awarded the 2013 Dijkstra Prize
Approximate inclusion-exclusion, N. Linial and N. Nisan, Combinatorica, 10(1990) 349-365.
Balancing extensions via Brunn - Minkowski, J. Kahn and N. Linial, Combinatorica, 11(1991) 363-368.
Improved routing strategies with succinct tables, B. Awerbuch, A. Bar-Noy, N. Linial and D. Peleg, Journal of Algorithms, 11 (1990) 307-341.
A combinatorial characterization of read-once formulae, M. Karchmer, N. Linial, I. Newman, M. Saks and A. Wigderson, Discrete Math., 114(1993) 275 - 282.
Results on learnability and the Vapnik Chervonenkis dimension, N. Linial, Y. Mansour and R. Rivest, Information and Control, 90 (1991) 33-49.
Online task systems, A. Borodin, N. Linial and M. Saks, Jour. Assoc. Comp. Mach., 39 (1992) 745 - 763.
Some extremal problems arising from discrete control processes, D. Lichtenstein, N.Linial and M. Saks, Combinatorica, 9 (1989) 269-287.
A lower bound for radio broadcast, N. Alon, A. Bar-Noy, N. Linial and D. Peleg, J. Comp. Sys. Sci., 43 (1991) 290-298.
Bounds on universal sequences, A. Bar-Noy, A. Borodin, M. Karchmer, N. Linial and M. Werman, SIAM J. on Computing, 18 (1989) 268 - 277.
A lower bound on the area of permutation layouts, A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial and A. Wigderson, Algorithmica, 6 (1991) 241-255.
On the cover time of random walks in graphs, J. Kahn, N. Linial, N. Nisan and M. Saks, Journal of Theoretical Probability, 2 (1989) 121-128.
Cycles of length 0 mod k in directed graphs, N. Alon and N. Linial, J. Combinatorial Theory ser. B, 47 (1989) 114-119.
Interpolation between bases and the Shuffle - Exchange network, N. Linial and M. Tarsi, European J. of Combinatorics, 10 (1989), 29 - 39.
Rubber bands, convex embeddings and graph connectivity, N. Linial, L. Lovasz and A. Wigderson, Combinatorica, 8 (1988) 91 - 102.
Some bounds for the Banzhaf index and other semivalues, R. Holzman, E. Lehrer and N. Linial, Math. Oper. Res., 13 (1988), 358 - 363.
Matroidal bijections between graphs, N. Linial, R. Meshulam and M. Tarsi, J. Combinatorial Theory ser. B, 45 (1988), 31 - 44.
Optima of dual integer programs, R. Aharoni, P. Erdos and N. Linial, Combinatorica 8 (1988), 13--20.
Extremal problems on permutations under cyclic equivalence, P. Erdos, N. Linial and S. Moran, Discrete Mathematics, 64 (1987), 1 - 11.
Legal coloring of graphs, N. Linial, Combinatorica, 6 (1986), 49 - 54.
Minimal non two - colorable hypergraphs and minimal unsatisfiable formulas, R. Aharoni and N. Linial, J. Combinatorial Theory ser. A 43 (1986), 196 - 204.
Graph coloring and monotone functions on posets, N. Linial, Discrete Mathematics, 58 (1986), 97 - 98.
Hard enumeration problems in geometry and combinatorics, N. Linial, SIAM J. on Algebraic and Discrete Methods, 7 (1986), 331 - 335.
Deciding hypergraph 2-colorability, N. Linial and M. Tarsi, Theoretical Computer Science, 38 (1985), 343 - 347.
Largest induced suborders satisfying the chain condition, N. Linial, M.Saks and P. Shor, Order 2 (1985), 265 - 268.
Twist boundary energies for metals with long ranged pairwise interatomic potential, R. W. Baluffi, A. Brokman and N. Linial, J. of Physics F: Metal Physics 13 L 127, 1983.
Every poset has a central element, N. Linial and M. Saks, J. Combinatorial Theory ser. A, 40 (1985), 195 - 210.
The information theoretic bound is good for merging, N. Linial, SIAM Journal on Computing, 13 (1984), 795 - 801.
Searching ordered structures, N. Linial and M. Saks, Journal of Algorithms, 6 (1985), 86 - 103.
Graph decomposition without isolates, N. Linial, J. Combinatorial Theory ser. B, 36 (1984), 16 - 25.
Extremal k-colorable subgraphs, L. D. Andersen, D. D. Grant and N. Linial, Ars Combinatorica, 16 (1983), 259 - 270.
Largest digraphs contained in all n - tournaments, N. Linial, M. Saks and V. T. Sos, Combinatorica, 3 (1983), 101 - 104.
The counterfeit coin problem revisited, N. Linial and M. Tarsi SIAM Journal on Computing, 11 (1982), 409 - 415.
A new derivation of the counting formula for Young Tableaux N. Linial, J. Combinatorial Theory ser. A, 33 (1982), 340 - 342.
Incidence matrices of subsets - a rank formula N. Linial and B. L. Rothschild, SIAM Journal on Algebraic and Discrete Methods, 2 (1981), 333 - 340.
Extending the Greene - Kleitman theorem N. Linial. J. Combinatorial Theory ser. A, 30 (1981), 331 - 334.
On Petersen's graph theorem, N. Linial, Discrete Mathematics, 33 (1981), 53 - 56.
Covering digraphs by paths N. Linial. Discrete Mathematics, 15 (1976), 297 - 300.
A lower bound on the circumference of a graph N. Linial. N. Linial, Discrete Mathematics, 15 (1976), 297 - 300.
Conference Papers not covered by Journal Articles

The influence of variables on boolean functions, J. Kahn, G. Kalai and N. Linial, 29th Symposium on the Foundations of Computer Science, White Planes, 1988, 68-80.
Graph products and chromatic numbers, N. Linial and U. Vazirani, 30th Symposium on the Foundations of Computer Science, North Carolina, 1989, 124 - 128.
Sphere packing and local majorities in graphs, N. Linial, D. Peleg, Yu. Rabinovich and M. Saks, 2nd Israel Symp. on Theory and Computing Systems (1993), 141 - 149.
A map of the protein space--an automatic hierarchical classification of all protein sequences, G. Yona, N. Linial, N. Tishby and M. Linial, Intelligent Systems for Molecular Biology Proceedings (ISMB) 6(1998), 212-221.

Ancient History

Generalized Fibonacci Nim (Hebrew), N. Linial, , This paper won the first prize at the 1969 Annual Shapira Contest, Weizmann Institute of Science. Here is the front page.
A Combinatorial Problem (Hebrew), N. Linial, Gillionot Lematematika 4 (1970),16-18.
An Extension of Young's Theorem (Hebrew) , N. Linial, Gillionot Lematematika 6 (1972), 9-14.