Wednesday, January 18, 2012

SODA review I: Talks, talks and more talks.

I asked Jeff Phillips (a regular contributor) if he'd do some conference posting for those of us unable to make it to SODA. Here's the first of his two missives.

Suresh requested I write a conference report for SODA. I never know how to write these reports since I always feel like I must have left out some nice talk/paper and then I risk offending people. The fact is, there are 3 parallel sessions, and I can't pay close attention to talks for 3 days straight, especially after spending the previous week at the Shonan meeting that Suresh has been blogging about.

Perhaps, it is apt to contrast it with the Shonan meeting. At Shonan there were many talks (often informal with much back and forth) on topics very well clustered on "Large-scale Distributed Computation". There were several talks earlier in the workshop that just overlaid the main techniques that have become quite powerful within an area, and then there were new talks on recent breakthroughs. But although we mixed up the ordering of subtopics a bit, there was never that far of a context switch, and you could see larger views coalescing in people's minds throughout the week.

At SODA, the spectrum is much more diverse - probably the most diverse conference on the theoretical end of computer science. The great thing is that I get to see colleagues across a much broader spectrum of areas. But the talks are often a bit more specific, and despite having usually fairly coherent sessions, the context switches are typically quite a bit larger and it seems harder to stay focused enough to really get at the heart at what is in each talk. Really getting the point requires both paying attention and being in the correct mind set to start with. Also, there are not too many talks in my areas of interest (i.e. geometry, big data algorithmics).

So then what is there to report. I've spent most of my time in the hallways, catching up on gossip (which either is personal, or I probably shouldn't blog about without tenure - or even with tenure), or discussing on-going or new research problems with friends (again not yet ready for a blog). And of the talks I saw, I generally captured vague notions or concepts. Usually stored away for when I think about a related problem and I need to make a similar connection, or look up a technique in the paper. And, although, I was given a CD of the proceedings, but my laptop has not CD drive. For the reasons discussed above, I rarely completely get how something works from a short conference talk. Here are some example snip-its of what I took away from a few talks:

Private Data Release Via Learning Thresholds | Moritz Hardt, Guy Rothblum, Rocco A. Servedio.
Take-away : There is a deep connection between PAC learning and differential privacy. Some results from one can be applied to the other, but perhaps many others can be as well.
Submatrix Maximum Queries in Monge Matrices and Monge Partial Matrices, and Their Applications | Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir
Take-away: There is a cool "Monge" property that matrices can have which makes many subset query operations more efficient. This can be thought of as each row represents a pseudo-line. Looks useful for matrix problems where the geometric intuition about what the columns mean is relevant. 
Analyzing Graph Structure Via Linear Measurements | Kook Jin Ahn, Sudipto Guha, Andrew McGregor
Take-away : They presented a very cool linear sketch for graphs. This allows several graph problems to be solved under a streaming (or similar models) in the way usually more abstract, if not geometric, data is. (ed: see my note on Andrew's talk at Shonan)

Lsh-Preserving Functions and Their Applications | Flavio Chierichetti, Ravi Kumar
Take-away: They present a nice characterization of what sorts of similarities (based on combinatorial sets), showing which ones can and cannot be used within a LSH framework. There techniques seemed to be a bit more general that for these discrete similarities over sets, so if need to use this for another similarity may be good to check out in more detail. 

Data Reduction for Weighted and Outlier-Resistant Clustering | Dan Feldman, Leonard Schulman
Take-away: They continue to develop the understanding on what can be done for core sets using sensitivity-based analysis. This helps outline not just what functions can be approximated with subsets as proxy, but also how the distribution of points affects these results. The previous talk by Xin Xiao (with Kasturi Varadarajan on A Near-Linear Algorithm for Projective Clustering Integer Points) also used these concepts. 

There were many other very nice results and talks that I also enjoyed, but the take-away was often even less interesting to blog about. Or sometimes they just made more progress towards closing a specific subarea. I am not sure how others use a conference, but if you are preparing your talk, you might consider trying to build a clear concise take-away message into your talk so that people like me with finite attention spans can remember something precise out of it. And so people like me are most likely to look more carefully at the paper the next time we work on a related problem.


  1. (I accidentally deleted Luca Aceto's comment: here it is)

    but if you are preparing your talk, you might consider trying to build a clear concise take-away message into your talk so that people like me with finite attention spans can remember something precise out of it.

    This is a very good piece of advice, regardless of the attention span of the audience.

    IHMO, having a take-home message is a must for every talk. I encourage all my students to think about the message they want to convey with their presentation and make it clear in the talk at least on one slide.

    If you have a clear message and deliver a clear presentation, people will remember it and will be more inclined to read the paper for the details, if they are interested in them. And if they do not, they will not think of listening to your talk as a waste of their brain cycles/time.

  2. To follow up on Luca's comment, I think people coming to big theory conferences still feel like they're giving a talk to a group of people that knows everything in theory, whereas this hasn't been true for a long time.

    It's time that we accepted that our field is too big for detailed talks, and that either you give a talk for your five colleagues, or direct a broader talk at a general audience that is mathematically sophisticated but possibly ignorant of your subfield.

  3. In my earlier comment, I forgot to mention John Baez's advice on giving good talks. It mentions Gian-Carlo Rota's Ten Lessons I Wish Had Been Taught, which is one of the sources I recommend to my students.


  4. Any comments about the fact the conference took place in Japan, that is, outside N America?
    Number of participants was very good, 1/3 from N America, 1/3 from Europe, and 1/3 from Asia, which seems to me like a great success.
    Unfortunately, many names typically coming to SODA didn't attend it this time, most likely because of the distance from the US, or the costs.
    Still, I found it very successful.
    And the organization was very good. Thanks to Kazuo Iwama.

  5. I was surprised to see again a discussion if papers from ALENEX and ALENECO should be now counted as SODA publications or not. I thought this proposal has been rejected last time, but it's been mentioned again, though I'm not sure if this will go through or not. To me, it's OK to have ALENEX and ALENECO and possible other conferences collocated with SODA, but I don't see why papers from these workshops should count as SODA papers.

  6. What were the actual attendance numbers? What were the numbers for SODA 2011 for comparison?

    Is it true that SODA 2014 will be in Honolulu? It seems that we are not choosing location to maximize attendance (i.e. try to find an affordable venue for max number of people) but to maximize the vacation for people with lots of grant money.

  7. Hawaii is far away, though not necessarily with very expensive hotels.

    SODA'12 has around 300+ participants, a very respected number. Notice that this is with almost no Chinese participants because of the Chinese New Year.


Disqus for The Geomblog