Tuesday, June 07, 2011

FCRC Continued

I've been enjoying FCRC;  of course, I like large conferences where lots of people show, as long as they're run well.  Rooms have been pretty full at the talks, and lots of people around to talk to.  I still don't understand why people object to the idea of making FOCS/STOC larger (and instead seem to prefer to create new conferences and workshops), but if that's the way the theory community wants it, I'd argue that more conference co-location is a good way to go.  

I thought Les Valiant gave an excellent Turing lecture -- I'm sure it will be online soon.  He provided a clear scientific challenge -- understanding how evolution could have accomplished so much in so little time (just several billion years) -- and made the case the computational complexity (and in particular learning theory) would be a necessary tool in developing an understanding to this problem.  I thought especially he did an excellent job gearing the talk to a general computer science audience, limiting the technical discussion and giving a broad overview of the importance of complexity theory, particularly as it might apply in this setting. 

Naturally, my favorite session so far has been the "randomized algorithms" session (1A) for STOC, including The Power of Simple Tabulation Hashing (Patrascu/Thorup), Tight Bounds for Randomized Load Balancing (Lenzen/Wattenhofer), and Social Networks Spread Rumors in Sublogarithmic Time (Doerr/Fouz/Friedrich).  The first paper shows that tabulation hashing, while only being 3-wise independent, can provide strong theoretical bounds (and excellent practical performance) for most of the natural application of hashing.  The second paper looks at parallel load balancing strategies, and shows that many of the lower bounds proven years ago can be beaten by loosening assumptions that led to the lower bounds in quite natural ways.  The third paper considered randomized rumor spreading in social network graphs, including the surprising result that taking care not to (randomly) send a message to the same neighbor in consecutive rounds changes the asymptotic behavior (to just barely sublogarithmic) in this setting.  All three of the talks were well-presented, making getting up for an 8:30 session worthwhile.

I'd have to say that the STOC poster session -- done for the first time -- seemed to be a successful experiment.  There were plenty of people around talking to the poster presenters, so much so that that it didn't seem to wrap up until more like 11 instead of the scheduled 10:30.  Hopefully students who presented will comment on how they liked the experience -- either on this blog, or, more directly, with e-mail to the organizers -- and let them know if they found it valuable.  I think getting students to present their work in this way will encourage and benefit them greatly and thereby strengthen the field.  


Grigory Yaroslavtsev said...

My experience about the poster session was truly great. It ended up being like giving 10-20 5-minute talks to very cool people with different background.

It's not that easy actually and very different from my previous experience, but was surely worth it. Probably, the main benefit is that you can very easily find people for future collaboration this way.

Thanks a lot to Salil and all other people who were involved into the organization of the poster session!

Justin Thaler said...

I'd like to (belatedly but enthusiastically) second Grigory's opinion. The poster session was a terrific experience -- it turned into a large number of short but substantive conversations, and I got to interact a number of people I might not have had a chance to talk to otherwise. I liked the informality of the event, and felt a strong sense of community, which might be a bit elusive for early graduate students experiencing the grind of the submission process for the first time. I also appreciated the session because I got a chance to talk about work that I hope many in the community find relevant, even though it's been submitted to several venues a bit off the radar of many theorists.

My one regret is that I didn't get to walk around and talk to the other presenters very much, but this seems unavoidable! Thanks to Salil and everyone else involved in the organization, and I hope the poster session remains a part of STOC/FCRC for years to come.