Broadcast talks from Cambridge

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.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Other and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s