Tuesday, March 31, 2009

When X is Enough

My advisor Joel Spencer derives pleasure from his result Six standard deviations suffice. The point of course is that often there is a pesky log factor in applications of the probabilistic method, and reducing it is a challenge, replacing it with an absolute constant is pure fun.

I was reminded of this when Meeyoung Cha pointed me to the SocialNets Conf she Chaired. One of the papers got my attention: Eight friends are enough. The paper argues that the Facebook tradition of showing eight friends in a profile page reveals far too much.



Anonymous TBW said...

Algorithmically this is great. Most global algorithms on massive networks are impractical. This means that local calculations would serve as a pretty good proxy for many global properties and thus speed up many computations

1:39 AM  

Post a Comment

<< Home