Centre Emile Borel’s metric2011 program is twinned with a parallel program, Discrete Analysis, running at the Isaac Newton Institute in Cambridge.

This means that participants are welcome to visit Cambridge (some financial support is available for that), especially to attend workshops. Also, Cambridge workshops will be, at least partially, broadcast in Paris.

This has started this week with the Embedding workshop, now running in Cambridge. Since Institut Poincaré does not have video equipment yet, the experiment is being conducted in a videoconference room lent by Université Pierre et Marie Curie, on the Jussieu campus. Next broadcast will be on Friday at 3pm, with a talk by Subhash Khot (New York University) on his UGC conjecture. Note that this conjecture, which has already sneaked in Claire Mathieu’s course (end of her first lecture), will wander around next week’s workshop in Paris, so a first exposition will be useful to all.

On monday, we could hear Nati Linial speak on Topology and probability? What a strange combination… This talk was an invitation to Nati’s forthcoming course in Paris. Starting from a problem posed by Gauss on the combinatorics of plane curves, Nati argued that a classical tool of combinatorics, probability (and notably, the probabilistic method) was relevant to topology. The paradigm is Erdös-Rényi’s theory of random graphs, and the following statement: if a random graph on n vertices is constructed by throwing an edge between any pair of vertices independantly with probability p, then the threshold probability for connectedness is log(n)/n. This means that if p is substantially smaller, the resulting graph is disconnected, and if p is substantially larger, it is connected.

Here is a sample higher dimensional problem, which is also motivated by computer theoretic considerations. Start with the complete graph on n vertices. Throw a 2-face through 3 vertices independantly with probability p, and get a simplicial 2-complex. Is there a threshold probability for simply-connectedness ? for the vanishing of homology ? I can’t tell you the answer, nor the contents of the sequel of the talk, since connection was interrupted by a computer collapse. So come and listen to Nati when he will be in Paris.

Yesterday, Yuval Rabani gave a talk on Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform. The Johnson-Lindenstrauss Transform alluded to means the following. Given a n-point subset X in a large dimensional Euclidean space, there is an orthogonal projection to a lower dimensional subspace (dimension is logarithmic in n) which nearly does not distort distances between points of X. This fact is useful for the design of embedding-based algorithms (as first observed by Linial-London-Rabinovitch in 1995). Yuval concentrates on finding constructions of such projections which can be computed in very short time when the given vectors (elements of X) are sparse.