It's still only the second day of conferencing for me (after yesterday at ALENEX) and I'm not yet exhausted, so I went to talks somewhat more frequently than the 1/3 of the time I suggested yesterday. But I would have been to maybe twice as many talks as I actually did go to if only they weren't all scheduled simultaneously. As Suresh tweeted, many of the talks have been quite good, although there have also been exceptions. I asked Cora Borradaile for her suggestions on how to be one of the good ones; her advice was to prepare what you think is a normal 20-minute talk, but then to keep only the first 10 minutes of material: usually even the bad talks start out ok, but then they get too technical and lose the audience.

I slept in (sorry, early morning speakers) and started my day with Yuval Shavitt's talk on counting subgraphs, because of its close connection to some of my own recent research. Specifically, Shavitt and his co-authors want to approximate the number of \( K_{1,s} \) subgraphs (stars) in a given graph. If one knows the entire degree distribution of the graph, this is easy, but they show how to do it while only randomly sampling a small fraction of the graph. By grouping nodes with similar degrees into buckets and sampling, one gets a rough idea of the degree distribution, enough to find most of the stars, but there could still be some unsampled buckets with a very small number of very high degree vertices. To find these, they do some more sampling to estimate the number of adjacencies between buckets with many vertices and buckets with few vertices; they also prove lower bounds showing that no such sublinear sampling method is possible for approximately counting only slightly more complicated subgraphs (triangles and length-3 paths).

Session 3 was one of the ones where I could easily have gone to talks in all three sessions, but I ended up in the geometric graph theory session. I was especially impressed with Tasos Sidiropoulos' talk on his work with James Lee, on partitioning bounded-genus graphs. The problem is to find a random distribution over a family of partitions of a given graph, for a given distance threshold \( R \), such that each set in each partition has diameter \( R \), but so that a pair of vertices at distance \( d \) has probability only \( \beta d/R \) of being separated, for a parameter \( \beta \) that is as small as possible; one can view the distribution as describing something sort of like an embedding of the graph into a metric space (the probability distributions describe an \( L_1 \) combination of simpler metrics defined by the individual partitions) in which \( \beta \) measures the distortion of the embedding. For arbitrary graphs the best bound on \( \beta \) is \( O(\log n) \), but for planar graphs it is \( O(1) \), and for \( K_t \)-minor-free graphs it is \( O(t^2) \); the minor-free bound implies that genus \( g \) graphs have \( \beta=O(g) \), but Lee and Sidiropoulos exponentially improve this to \( O(\log g) \). The main idea is to combine tools from three previous papers in a clever way: a method of Erickson and Whittlesey for (deterministically) finding a collection of \( O(g) \) shortest paths that cut the bounded-genus surface into a disk, the \( \beta=O(1) \) method for the planar part of the input that is at least a random multiple of \( R \) away from the shortest paths, and a method by Kalinescu, Karloff, and Rabani for achieving the general \( O(\log n) \) bound by forming radius-\( O(R) \) bubbles around a sequence of randomly selected points of the metric space. If one instead forms long thin radius-\( O(R) \) bubbles around randomly ordered paths of the cut set, and then slices these bubbles into diameter-\( O(R) \) pieces, the \( O(\log n) \) bound turns into \( O(\log g) \). Apparently this leads to improvements in a large number of approximation algorithms for bounded genus graphs.

I also enjoyed the talk by Koivisto or Parvainen (I walked in a minute late and didn't catch which of them presented it) on algorithms for problems such as the traveling salesman problem or feedback arc set that can be solved by finding an optimal permutation of the vertices (e.g. for feedback arc set, the cost of the solution is the number of edges that are oriented from a later vertex in the permutation to the earlier one). I posted a couple years ago about the (approximately) \( 2^n \) time and space dynamic programming algorithm for TSP, at which time Thore Husfeldt and Ryan Williams told me about a different solution which uses only polynomial space but \( 4^n \) time: for each partition into two equal subsets of vertices, recursively find the optimal tour that goes first through all the vertices on one side of the partition, and then through all the vertices on the other side. But \( 2^n \) space is too much (the algorithm will run out of space for problem sizes on which it is still reasonably fast) and polynomial space is too little (the time becomes the bottleneck for problem sizes where the memory usage is a tiny fraction of what's available). By switching to dynamic programming when the recursion gets to small enough sets, one can get a tradeoff between time and space, but one in which the product of both is still \( 4^n \); this paper finds a better tradeoff with a smaller product. The idea is to find a family of partial orders whose linear extensions together cover all permutations, and to loop through these partial orders, for each one doing dynamic programming in the associated distributive lattice of lower sets to find the optimal linear extension. The time is the sum of the sizes of the lattices, and the space is the maximum width of any of these lattices; the hard part (and the part where perhaps there is still more interesting research to be done) is finding the right collection of partial orders (or possibly more general structures such as antimatroids).

Quote of the day, from Daniel Lokshtanov in the first of his two (both good) talks on fixed-parameter-tractable algorithms: “Some polynomials are more polynomial than others.” The context was a comparison of time bounds for problems like max cut on graphs of bounded cliquewidth; a bound of the form \( f(c)n^{O(1)} \) is more polynomial than one of the form \( n^{O(\log c)} \), which is more polynomial than \( n^{O(c)} \), etc.

And, as with yesterday's post, to end with something not-quite-on-topic for the conference: texting while your professor is lecturing vs twittering while some researcher is giving his or her SODA talk: is one more inappropriate than the other?