Aravind's White Board Talk
I heard Aravind talk recently about the Lovasz's Local Lemma (LLL). He spoke about the results in his JACM paper that builds on Moser and Tardos and gives improved constructive versions of LLL. In particular, they show an algorithm that is poly time in the number of underlying variables (and not in the total number of events) by looking at the core/kernel of the variables that define the events. He also spoke about some more recent work, but alas I spaced out. The whole body of work has a bunch of nice applications, eg, to the Santa Claus problem or the classic routing result of Leighton, Maggs and Rao (which I was happy to be reminded after so long!). In general, Aravind's talk was nostalgic with the Rodl's nibble, FKG and Janson's inequalities and other probabilistic tools. Aravind is a master, not only in applying these methods when they are effective and extending them, but also quite comfortable in ``inverse'' step of hacking complex problem spaces into portions where these tools can be applied. Aravind is a poly-algorithmicist, and beyond his work in combinatorics, graph theory and probability, he has some nice stuff in networking, auctions and social structures as well.