COCOON 09

I was at COCOON, held at an edge of US, where the Niagara river goes over. I got there in time to hear Venkat's very nice talk on inapproximability of certain ordering problems like maximum acyclic subgraph (MAC) and permutation CSP. A message was that it is hard to beat random ordering (for MAC), and Venkat gave a lot of intuition into formulating the notion of "approximation resistance" (CSP). He also described the larger context of UGC hardness and approximating CSP problems via SDP, established by Raghavendra. I wanted to give a talk on Configuration Auctions, but ended up giving a more general talk on Internet Ad Auctions. I will put slides up soon. One of the nice things about theory conferences, no matter which one, there are always nice problems/techniques one hears.

SUNY Buffalo, the local host institution, is associated with quality theory in my mind. I got to talk to Atri Rudra and heard about some of his nice new results on codes in the streaming model. I also had a great talk with Hung Ngo on analyzing probabilistic data, wish I had more time to talk about some networking problems.

Finally, I completed nearly 20 years of my life as an immigrant in NY by visiting the Falls for the first time. I am a freak for large bodies of water, and the simulated waterboarding as you stand under one of the falls and gasp as your lung expands, was cool. Also, I got reminded that we all have reasons why we are theory researchers. Me, I left my undergraduate school vowing never to read another IEEE journal again. With the exception of some amazing thing by information theorists, for most past, I have succeeded.