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:

ISI Highly cited, MathSciNet, DBLP, Google Scholar. .

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

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

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

Upper bounds on the number of Steiner triple systems and 1-factorizations, Nati Linial and Zur Luria.
Leapfrog in posets (note) Amir Ban and Nati Linial.
Collapsibility and vanishing of top homology in random simplicial complexes Lior Aronshtam, Nati Linial, Thomasz Luczak and Roy Meshulam.
An upper bound on the number of high-dimensional permutations, Nati Linial and Zur Luria.
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.
Published Papers

No justified complaints: On fair sharing of multiple resources, Danny Dolev, Dror Feitelson, Joe Halpern, R. Kupferman and N. Linial, ITCS 2012, to appear.
Oblivious collaboration, Yehuda Afek, Yakov Babichenko, Uri Feige, Eli Gafni, Nati Linial, and Benny Sudakov. DISC 2011, to appear.
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, 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, accepted for publication.
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, accepted for publication.
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.
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.
ProtoMap: 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.
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.
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

N. Linial, Generalized Fibonacci Nim (Hebrew), The Annual Shapira Contest, Weizmann Institute of Science, 1969 (First Prize).
N. Linial, A Combinatorial Problem (Hebrew), Gillionot Lematematika 4 (1970),16-18.
N. Linial, An Extension of Young's Theorem (Hebrew), Gillionot Lematematika 6 (1972), 9-14.