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.

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

Israel Journal of Mathematics, Editorial Board (Chief Editor 2013-2017).

Random Structures and Algorithms, Editorial Board.

Combinatorica, Editorial Board.

Table of content

Introduction

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Chapter 8

Chapter 9

Appendix

Index

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.

Expanders, (in Hebrew)

On the limitations of human knowledge, (in Hebrew).

Euler and the magic of numbers, (Powerpoint presentation, In Hebrew,

Randomness - Friend or foe?, (Powerpoint presentation, In Hebrew,

Ten milestones in the history of mathematics, (With Gil Kalai, In Hebrew,

ProtoNet

EVEREST

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.

Computational Molecular Biology

Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson,

Finite Metric Spaces - Combinatorics, Geometry and Algorithms, N. Linial,

Game-Theoretic Aspects of Computer Science, N. Linial, in "

(R. J. Aumann and S. Hart eds.) North Holland, 1994, pp. 1340-1395.

Generalized Fibonacci Nim (Hebrew)