Tuesday, January 24, 2006

SODA Day III.

I will attend more talks next year...
I will attend more talks next year...
I wil attend more talks next year...

The morning session talks were moved from their original location because of flooding in the conference room. No, I am not making this up.

So we reach day 3, and by now most people have given up the pretence of attending talks. Alan Frieze's invited lecture on random graphs was packed though. Most of you probably know what random graphs are: briefly, imagine a graph generated by adding an edge between any pair of vertices with probability p.

There are all kinds of interesting properties one can prove on random graphs. One of the most striking is a sharp "phase transition" that occurs in connectivity, going from a mostly disconnected graph to a connected one, as p gets large enough (slightly larger than log n/n). Random graphs have become a useful way of modelling the Web graph: for example, the preferential attachment process of Barabasi and Albert defines a random graph whose degree sequence follows a power-law, and that mimics many properties of the Web graph.

This was probably the most technical of the three talks, and had (at least hints of) some seriously cool methods in probabilistic analysis. I'll link to the talk when it comes online.

Outtakes:
  • One of the "pitfalls" of being known as the geomblogger is that when I sit down with my laptop, the default assumption appears to be that I am blogging about the conference.

Categories:
Post a Comment

Disqus for The Geomblog