Some talk highlights from WADS

Here again are a few highlights of some talks that caught my attention, this time at the Algorithms and Data Structures Symposium. WADS is held every two years, somewhere in Canada; this time it was at Western University in London, Ontario. With typical Canadian modesty WADS was originally called a workshop instead of a symposium, giving it its acronym, but they still haven't figured out a new meaning for the W in the years when it isn't in Waterloo or Winnepeg.

Slime molds

In the first of three invited talks, Kurt Mehlhorn talked about these creatures, which have a single cell shared by many nuclei and can be as large as a human hand. They tend to spread out into shapes resembling a network of tubes, through which nutrients and other cellular material flows in a pulsating action. When spread between two food supplies, these networks converge in polynomial time to a shortest path connecting the two terminal points. However, with larger numbers of connection points, they form more complex structures that resemble human-designed train systems.

Blame trees

Edward Yang, a student in programming languages at Stanford, gave the talk on "Blame trees", a paper he wrote with Erik Demaine and several other co-authors based on research he did as an undergraduate at MIT. It takes a data-structures approach to the problem of merging different versions of a repository in a distributed version control system such as git or mercurial. Viewed in this way, the problem is persistent (all the old versions of the repository are accessible) and more specifically confluently persistent (a merge combines more than one old version). The authors view repository files abstractly, as ordered sequences of pieces of data (e.g. lines of code), each of which is tagged with the version at which it was added to the document. The result of merging two versions should be a sequence of lines that includes the ones that are newly added in either version as well as the ones that are common to both versions, with a merge conflict when this sequence is ambiguous. Existing systems which take at least unit time per line to perform a merge; in comparison, their new blame tree structure takes logarithmic time for each contiguous block of shared lines, which could possibly be much smaller. But it's not yet clear whether it would be a practical improvement, nor is it obvious how such a system could be retrofitted into existing systems: the file storage system that underlies the repository would need to be completely rebuilt.

Counting subgraphs

Because of some visa issue, authors Zdeněk Dvořák and Vojtěch Tůma could not come to WADS, so Csaba Tóth presented their paper, "A dynamic data structure for counting subgraphs in sparse graphs". The problem they consider is to maintain a large graph \( G \) and determine how many copies of a small target graph H it contains; here a "copy" may mean an isomorphic subgraph, an induced subgraph, or a graph homomorphism. I had previously worked on the same problem, with Emma Spiro and others, with the goal of speeding up the ERGM method for generating random networks that resemble social networks. Because of this application, we made only weak assumptions about \( G \) (namely that it has low h-index), and were only able to handle very small targets (three or four vertices). Dvořák and Tůma make stronger assumptions about the sparsity of \( G \) and get much more general algorithms, able to handle target graphs of any bounded size. It's another nice example of the theory of shallow minors developed by Nešetřil, Ossona de Mendez, and others, where an \( r \)-shallow minor is a graph obtained by contracting trees of radius at most \( r, \) and then deleting some edges and vertices. For graphs of bounded expansion (the \( r \)-shallow minors have edge density bounded by a function of \( r \)), the time per update is polylogarithmic, while for nowhere dense graphs (the \( r \)-shallow minors do not include arbitrarily large cliques) it's subpolynomial.

Shaving logs

Timothy Chan gave another invited talk, on reducing the running time of algorithms by logarithmic factors. When the algorithm in question has a running time like \( O(n^c \log^d n), \) this can often be accomplished by tightening the data structure that causes the polylog factor in the time, but reducing time bounds like \( O(n^c) \) to \( O(n^c/\log n) \) requires more specialized techniques, which Timothy grouped into problems with no weights, integer weights, and real weights. The model of computation for these problems is essentially the same unit cost RAM that is used for most algorithms research, in which data is stored in machine words (of at least logarithmically many bits else you couldn't index memory) and word operations take constant time each. Timothy defended the algorithms in question as "not cheating" by reference to this model, but I think a stronger non-theoretical argument is possible: you can implement many of these algorithms and the match between their actual and predicted runtime will be in the same ballpark as any other kind of algorithm.

Many unweighted problems can be solved by the Four Russians technique (named after its inventors, some but possibly not all of whom were actually Russians). Basically, this means packing multiple input items into machine words and then using word operations and table lookups. Timothy discussed the application of this idea to Boolean matrix multiplication (the original idea of the four Russians) but this has the disadvantage of being obviated by fast matrix multiplication. The version I'm more familiar with is for longest common subsequences (Masek and Paterson 1980). It replaces the computation of square submatrices of logarithmic side length in a dynamic programming array by single table lookups (indexed by the values on the top and left sides of the submatrix and producing as a result the values on the bottom and right sides). As a result it shaves not one but two log factors.

As a typical integer-weight problem, Timothy considered 3SUM, in which one is given as input three lists \( A, \) \( B, \) and \( C \) of numbers and the goal is to find three elements \( a, \) \( b, \) and \( c \) in these lists with \( a+b=c. \) The problem can be solved in \( O(n^2) \) time by sorting \( A \) and \( B \) and doing a linear scan to test whether any element of \( C \) can represented as a sum. In an earlier WADS, Baran, Demaine, and Pǎtraşcu showed how to use linear hashing to speed this up: if the numbers in all three lists are all transformed by the same linear hash function to a smaller range, then solutions of the original problem remain as solutions of the hashed problem, but some additional false positives might be formed. Blocks of consecutive numbers in the sorted lists can be packed into a single word, and table lookups can be used to search for solutions a block at a time rather than a single value at a time. By choosing the hash values in the appropriate range the number of false positives can be kept manageably small while still allowing large enough blocks of numbers to be packed together to get a speedup. One of the open problems from Timothy's talk was to get a similar speedup for real-number rather than integer inputs.

Log shaving can be done in exponential algorithmics as well as in the polynomial regime, and in this case the log that is shaved may be a log of an exponential (that is, a linear or polynomial factor). In this case, one of the more powerful techniques is to prove the existence of shallow decision trees. For instance, a paper of Fredman from 1976 shows that the all-pairs shortest path problem (or quivalently min,plus matrix multiplication) has decision trees of depth \( O(n^{2.5}), \) better than the \( O(n^3) \) of the obvious algorithms. This doesn't directly give an algorithm that will run that fast, but it means that some savings is possible by dividing into many small subproblems and using a single precomputed decision tree for those subproblems. Timothy observed that the Bellman–Held–Karp dynamic program for the traveling salesman problem reduces to highly-unbalanced (min,plus) matrix multiplications, so this technique can be used to speed it up from \( O(n^2 2^n) \) to \( O(n^{3/2} 2^n) \)\. This requires an assumption that machine words have linearly many bits (rather than logarithmically many), which may seem unrealistic, but the same assumption is needed in the unshaved version of Bellman–Held–Karp.

Unversal point sets

Csaba Tóth spoke again, this time on his own research with Radoslav Fulek on universal point sets for plane 3-trees. These are the graphs that can be formed by recursively subdividing triangles into triples of triangles, but a stretching transformation (also used in my own recent work on universal point sets) converts this to a problem of recursively subdividing rectangles into triples of rectangles. If one did this in a grid of quadratic size, it would be possible to do each subdivision step in such a way that each rectangle had area proportional to the number of vertices to be placed in it, but Tóth and Fulek instead use a grid in which certain squares have been hollowed out, leaving only the points on the main diagonals. To handle this modified grid, they round up the dimensions of large rectangles, and then switch to a different strategy for small rectangles. The result is a universal point set of size \( O(n^{5/3}) \) for these graphs. It's the first subquadratic bound known for them, but there's no reason to expect that it's the right bound: the actual minimum size of their universal point sets could plausibly be much smaller.

All nearest smaller values

Tetsuo Asano gave the last talk of the conference, but spoke hopefully about it not being the last in his career (he is rapidly nearing retirement). Actually, he and David Kirkpatrick worked on all nearest larger values, but it's the same thing as ANSV. The problem has many applications; for instance, a monotone mountain (a polygon with a flat base side and with the remaining sides forming the graph of a piecewise-linear function over that base) can be triangulated by connecting each vertex to its left and right smaller neighbors. Asano and Kirkpatrick's work concerned computing these neighbors in sublinear space (possibly out of order). For computing the nearer of two neighbors, it's possible to search simultaneously in both directions until finding something smaller, giving a total of \( O(n\log n) \) time; computing the nearer neighbor in only one direction is more complicated, but ends up with a similar time bound. They also found a tradeoff between the amount of memory needed and the slowdown relative to the linear-memory linear-time algorithm. Low-space construction of Cartesian trees (in which each value in an array is connected to the larger of its two nearest smaller neighbors) seems to be still open.

Comments: