The FOCS accepted abstracts are out and Kintali has pointers to online copies of the papers. A few that caught my attention:

  • A non-linear lower bound for planar epsilon-nets, Alon. If \( S \) is a set of points in some geometric space, and \( R \) is a set of shapes (e.g. all possible axis-aligned rectangles in the plane), then an \( \varepsilon \)-net is a subset of \( S \) that hits every "large" shape, where a shape is large if it includes an \( \varepsilon \) fraction of \( S \). These things are very useful in making geometric algorithms deterministic, because they can often be used in place of random samples from \( S \). The size of an \( \varepsilon \)-net turns out to depend only on \( \varepsilon \) and not on \( S \): a general upper bound shows that for many reasonable sets of shapes, this size is \( O(1/\varepsilon \log 1/\varepsilon) \) but in a few cases better bounds of the form \( O(1/\varepsilon) \) were known. This paper shows that such good bounds cannot hold more generally.

  • Subcubic equivalences between path, matrix, and triangle problems, Williams and Williams. Although there are fast matrix multiplication based techniques that work well for graphs with small integer weights, for decades there hasn't seemed to be anything much better than cubic time in the worst case for all pairs shortest path problems on arbitrarily weighted directed graphs. This paper shows that there is a collection of many path problems including APSP that are all stuck in the same boat: an improvement to one of them would improve the rest as well. The problems include negative cycle detection, finding triangles, and the \( k \)-shortest simple paths problem (even in the special case \( k = 2 \)).

  • On the queue number of planar graphs, Di Battista, Frati, and Pach. Suppose that we maintain a set of \( k \) queue data structures and, at each of \( n \) time steps, perform some number of enqueue and dequeue operations on distinct items. Draw a graph that has the time steps as vertices and that has an edge between the enqueue time and the dequeue time of each item. Then this graph has queue number \( k \). The stack number can be defined analogously, and is the same as the pagenumber or book thickness; it's known that planar graphs have pagenumber at most \( 4 \). This paper shows that the planar graphs also have polylogarithmic queue number, and they use this result to find low-volume 3d grid embeddings in which no two edges intersect. It's unusual to see graph drawing research in FOCS but this looks like a nice result.