Wednesday, November 28, 2012

NY Area Theory: A day of theory turns 30

Zvi Galil started something a while ago: an annual one-day meeting at Columbia Univ in NY, get the best theory people to speak an hour each on some of the best theory results, often the recent/emerging/nascent ones. In one case, I remember Rao Kosaraju going through a proof with symbols a,...,k and missing a few eg., f, i, ... because he didnt need them once they were used in the intermediate versions of the proofs (which I am sure he did on the Amtrak train up from MD to NY! :)) Zvi set a high bar for a day of theory.

I sorta remember the white T-Shirt for the 25th anniversary of the day,  five palm imprints in black, graffiti style. The meeting is now semi-annual, and called the NY Area Theory Day, and its 30th edition takes place this Friday. The list of speakers looks awesome. Enjoy!

Labels:

Wednesday, November 07, 2012

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.

Story of the Flood

A classic short story in its entirety: "When he awoke, the dinosaur was still there."

What I lost in my NY apartment due to the flooding by Sandy:

Half a lifetime of all the paintings I did, gifts I got, photos I took and things I made. Now I can go to the afterlife clutching only my research papers to show.