I’m in Edmonton, Canada for WADS, which just finished, and CCCG, which is just about to begin.

The three invited talks at WADS were by Rasmus Pagh, Bob Tarjan, and me. Pagh spoke on methods for representing sets of elements by concise sketches so that the size of intersections or unions of the sets could be rapidly and accurately estimated. A famous method for this is MinHash, in which one represents a set by the \(k\) elements with the smallest values of some hash function; the size of the overlap in representations is then an accurate estimator for the Jaccard similarity of pairs of sets. New to me were \(1\)-bit variations of MinHash, in which you can get almost as accurate a representation in much less space by mapping each element of the MinHash set to \(\{0,1\}\) by another hash function. This works well when the Jaccard similarity is bounded away from both \(0\) and \(1\), and Pagh spoke about some recent research he and others had done on finding even more accurate methods when it is near \(0\) or near \(1\).

Tarjan spoke about parallel algorithms for connected components in graphs, an old area but one in which apparently there have been frequent published mistakes. He presented a modular analysis of the algorithms in this area according to some basic operations they perform (hooking together roots of trees on components, propagating that root information downwards through the trees, flattening the trees to make the information propagate more quickly, and the like) and showed that simple combinations of these operations lead to new, simple, efficient and more importantly provably-correct algorithms.

My talk, “Graphs in Nature”, was about finding graph-theoretic characterizations of surface-embedded graphs arising in natural processes, and using those characterizations to find algorithms to reconstruct synthetic geometric structures of the same type from their graphs. I also gave roughly the same talk a month earlier, at the Symposium on Geometry Processing in Milan. I’ve put my talk slides online in case anyone else is interested.

The best paper award went to Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo and Srinivasa Rao Satti for their paper “Succinct Data Structures for Families of Interval Graphs”. I can’t tell you much about the talk because, unfortunately, I missed it. I didn’t know it was the best paper until the business meeting that evening, so I went to the other parallel session instead.

I think the contributed talk from Tuesday that most stood out to me was Bryce Sandlund’s, on offline dynamic graph algorithms. This is a type of problem I worked on long ago for minimum spanning trees in which you get as input a whole sequence of edge insertions and deletions in a graph, and must produce as output the sequence of changes to the solution to whatever you’re trying to solve. Bryce’s new paper with Peng and Sleator solves similar problems for higher-order graph connectivity. The main idea is to hierarchically decompose the update sequence into intervals, and then represent the non-dynamic part of the graph within each interval by a smaller equivalent replacement graph whose size is proportional to the interval length. At the end of his talk, Bryce hinted that he could also solve incremental problems (where the updates are given one at a time rather than all in advance, but are only insertions) using similar methods in a forthcoming paper.

I was inspired by Caleb Levy’s talk on splay trees (in which he showed that inserting elements in either the preorder or postorder of another binary search tree takes linear time) to ask the following question: we know either by time-reversing the tree rotation operations or from the geometric model of dynamic search trees that any given access sequence should have the same optimal cost as its reverse. So from the dynamic optimality conjecture it should also be true that (up to constant factors) splay trees have the same performance on the reverse of any access sequence as they do on the unreversed sequence. Can this be proven?

From the business meeting, we learned that attendance and paper submissions were down by around 15% from the previous WADS. The acceptance rate is roughly the same, just under 50%. I suspect the smaller size is because the location is not as appealing, but it turns out to be a perfectly pleasant place to have a conference: the weather in Edmonton is pleasant this time of year (except for the thunderstorm), and there are abundant restaurants, good coffee shops, and lodging within walking distance of the conference center. WADS alternates with SWAT, which next year will be in the Faroe Islands. And then WADS 2021 (and CCCG 2021) will be in Halifax, Nova Scotia, which is both more touristy than Edmonton and easier to reach from the east coast and Europe. So I suspect the numbers will improve again.

WADS is moving towards a more democratically elected steering committee formed from some combination of past PC chairs and at-large elections. They have already started implementing the SafeTOC recommendations for combatting harassment and discrimination in theory conferences. And in a show of hands at the business meeting, the attendees were strongly in favor of moving towards double blind peer review for submissions. The conference is not really open access, though (its proceedings are published by Springer LNCS with special issues in Springer’s Algorithmica and Elsevier’s Computational Geometry) and there seems to be little pressure for that to change any time soon.

On to CCCG!

(Discuss on Mastodon)