SODA Day 2.

I seem to be the only person blogging about SODA (even though Jeff, Glencora and Sorelle were around as well - come on people !)

SODA Day 2 was the official day for bidimensional dimensionality reduction in spaces of bounded doubling dimension (ok that almost made sense). Here are some highlights:

• I enjoyed Bidimensionality and EPTAS not because of the results themselves (which are interesting) but because the talk was great, and I learnt a lot about the basic framework of bidimensionality. The talk was low on technical details, but the main contribution of the paper is a stronger result connecting bidimensionality of a graph property to the existence of an (E)fficient PTAS for the problem. Earlier work needed a constant factor approximation algorithm to bootstrap the process, and they were able to relax that assumption.
• In the same session, Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal was also cool. They showed that any progress on improving the exponential dependence on treewidth for a number of parametrized problems (for example from 2^tw to (2-eps)^tw) would break the Strong Exponential Time Hypothesis (i.e that SAT cannot be solved in (2-delta)^n time). 
• A paper that drew a lot of attention (as seen by the huge influx of people into the room) was the work by Daskalakis and Papadimitriou (Christos gave a really great talk) on Continuous Local Search. In brief, they constructed a complexity class that combines the approximate fixpoints of PPAD and the local search of PLS and contains some natural problems from algorithmic game theory as well as numerical analysis. Indeed, gradient search can be viewed as a special example of elements of this class.
• There was a whole session on approximate geometry, and doubling dimension played a key role in constructing efficient spanners, and in getting below the JL limit. Sandwiched between these was a local JL embeddability result, the idea being that if you only care about preserving distances in your (k)-neighborhood, you can get dimensionality reduction in terms of k, rather than n. The proof itself uses a variant of the Nash embedding theorem.

SODA Day 1.

I'm slowly unloading my backlog of posts on SODA 2011. At this point, the purpose is less to be a live-stream of events, and more to be a reflection on things I found interesting. As always, there will be no attempt to be deep, insightful or comprehensive. If you think I've missed THE PAPER OF THE YEAR berate me in comments and then write a guest post :)

The Holiday Inn has two major problems. Firstly, the conference rooms were in the basement, which meant that 3G access was hard to come by. Secondly, the local wifi wasn't particularly strong, and didn't work too well in the rooms or in the higher-up hotel rooms. This unfortunately forced me to actually listen to talks rather than tweeting about them. Good for the conference, bad for the as many as TWO WHOLE people who couldn't attend the conference and were hanging on my every tweet waiting for updates.

•  T. S. Jayram and David Woodruff had an interesting paper on JL transforms beyond the constant error rate. One of the standard methods in JL proofs is to prove a constant error bound for distortions, and then use multiple parallel copies to reduce the error down to 1/n^2 so that the union bound can kick in. The question is: is this the optimal thing to do ? Might some more clever scheme avoid the need for parallel copies ? Their answer, it turns out, is no. They show lower bounds that match the best upper bounds, and in the process develop a new technique that gives lower bounds for communication complexity that depend on the error probability as well as the approximation guarantee.
• The next paper in the session also introduced a new tool for communication complexity lower bounds. Elad Verbin and Wei Yu proposed a generalization of Boolean Hidden Matching (which was used to separate quantum and classical communication complexity) and used it to show new streaming lower bounds for sorting by reversals, among other problems.
• A talk I didn't attend, but should have (DABSH), was by Flajolet, Pelletier and Soria on Buffon machines. You can think of the Buffon needle process as a way of generating $2/\pi$. So the question they answer in this paper is: what kinds of "simple processes" can generate other complicated functions like exponentials, trigonometric functions and the like.
• Continuing the 'analytic combinatorics' theme, Wojciech Szpankowski talked about his paper with Michael Drmota on discrete divide and conquer recurrences. The main results of the paper were quite neat: a master theorem like formulation to solve exactly recurrences that involve floors and ceilings, without resorting to domination arguments. The advantage is a more precise bound on the running time which also captures the herky-jerky behavior of such algorithms (because of uneven integer splits)

I didn't get as much out of Bruce Reed's talk as I would have liked, mostly because I made the mistake of sitting in the back and could only see half of each slide. The talk itself was rather technical, with less of the high level intuition that might be helpful to an outsider to this area like me. It is however a reasonable model for an invited talk.

If it's Sunday at SODA, it's NFL time. As usual, Kirk Pruhs wandered around wearing his Steelers shirt, and looking mighty pleased. David Johnson was alternately elated (Packers win !) and downcast (Jets lose !) and a number of us drifted towards the hotel bar by early evening to set up shop there in front of the big screen. For those of you sniffing disdainfully at my embrace of brutal American sports, I'll merely say that there are MANY football fans among the SODA community.

Postscript: I was feeling guilty about summarizing papers so briefly. I just found Oded Goldreich's page on papers he's interested in (via this cstheory question) and it appears to be a nice model with short comments on papers he likes.  I might try doing something like this either interspersed with other posts here, or on my web page, just to force me to read papers of interest.