Friday, July 17, 2009


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.



Anonymous Anonymous said...

It would be nice if venkat could make the results of his talk public, i.e. the second paper he talked about is not publically available yet.

10:17 AM  
Blogger S said...

I looked for the CSP paper in CCC09 before posting, but could not find it online. Will ping the authors.

-- metoo

6:43 AM  

Post a Comment

<< Home