Many people have asked to to update my complexity pages with a bit of theoretical background to to support some of the material there (in particular, percolation theory). So, as promised, I've updated
http://www.maoz.com/~dmm/complexity_and_the_internet with a little (very little) bit of material on percolation theory. Questions and comments on all of this very much welcomed, Dave