Many of the basic algorithmic questions deal with the geometry of graphs. We know many variations on the theme of computing the metric of edge-weighted graphs. E.g., “all-pairs shortest paths”. As I will try to convey in this lecture, there is much that we know beyond that as well as broad barely charted territories. For example, let G=(V,E) be a graph and let w(e)>0 be given positive real numbers associated with every edge e in E. Geerically over the choice of the positive real numbers w(e) (i.e., with probability 1), this w determines a unique shortest path P_uv between any two vertices u,v in V. We put the weight system w in the same equivalence class as weight system w’ if the two weight systems determine the exact same system of paths. We still do not know which graphs have the largest number of such equivalence classes and how large this number can be.The more technical part of my lecture is based on recent papers with my student Daniel Cizma. A path system in a graph is said to be consistent if it is closed under taking subpaths. Clearly path systems that come from edge lengths are consistet but as we show, the reverse implication is far from being true.
Nati Linial is a full professor at the School of Computer Science and Engineering in the Hebrew University of Jerusalem.
He has a B.Sc. from the Technion and a Ph.D. from the Hebrew university, both in mathematics.
He works on bridging mathematics and theoretical computer science, and specializes in: Combinatorics; The Theory of Algorithms; Applications of Geometry and Analysis to the above fields; Computational Molecular Biology.
http://www.cs.huji.ac.il/~nati/