The list of FOCS acceptances (with abstracts!) is public; thanks to Suresh for letting me know via Google+.

It looks like a good program; quite a few of the titles caught my attention. Here are ten of them, with preprint links when I could find them:

"The minimum k-way cut of bounded size is fixed-parameter tractable", Mikkel Thorup and Ken-ichi Kawarabayashi, arXiv:1101.4689. The problem: given a graph, a number \( k, \) and another number \( s, \) we want to remove at most \( s \) edges from the graph so that the remaining subgraph has at least \( k \) components. They show that for any fixed \( s \) it can be solved in quadratic time.

"Fully dynamic maximal matching in \( O(\log n) \) update time", Surender Baswana and Manoj Gupta and Sandeep Sen, arXiv:1103.1109. Allows edges to be added or removed from a graph while maintaining a maximal matching. Addition is trivial so the hard part is handling removals. Dynamic graph algorithms have been relatively rare at algorithms conferences lately so it's refreshing to see one here, with clean bounds for a natural problem.

"Solving connectivity problems parameterized by treewidth in single exponential time", Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Michał Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk, arXiv:1103.0534. They solve problems like Hamiltonian path and Steiner tree in time singly exponential in the treewidth of the input graph, surprisingly since the natural dynamic programs for these problems do not have a singly-exponential number of states.

"Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications", Christian Wulff-Nilsen. It's known that minor-closed graph families obey a separator theorem whose constant factor depends linearly on the size of the forbidden minor, but the algorithms for finding these separators are not practical. This paper produces worse separators more quickly.

"3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General", Timon Hertli, arXiv:1103.2165. Last December I mentioned a paper of Iwama et al. at ISAAC 2010 on 3-SAT that trades off between two different approaches to the problem, one that is good when there are many solutions and one that is good when there are few, taking time \( O(1.32113^n) \) in the worst case. This new paper is based on the few-solution side of the problem and knocks the time bound down to \( O(1.308^n). \)

"On Range Searching in the Group Model and Combinatorial Discrepancy", Kasper Green Larsen, (preprint). Improves the lower bounds for some important geometric data structural problems.

"A Polylogarithmic-Competitive Algorithm for the \( k \)-Server Problem", Nikhil Bansal and Niv Buchbinder and Aleksander Madry and Seffi Naor. There's a phenomenon in online algorithms where randomized algorithms can sometimes be exponentially better than deterministic ones; for instance, in page replacement strategies for virtual memory, any deterministic strategy is at best k-competitive (where \( k \) is the number of pages of real memory available) while randomized strategies can be \( O(\log k) \)-competitive. This paper shows that a similar phenomenon happens for the \( k \)-server problem, an abstract problem that can model page replacement and many other more specific application problems, as long as there are not exponentially many distinct requests possible.

"Minimum Weight Cycles and Triangles: Equivalences and Algorithms", Liam Roditty and Virginia Vassilevska Williams, arXiv:1104.2882. They reduce the problem of computing the girth of a graph with small-integer edge weights to finding a triangle in a derived graph, which lets them apply known triangle-finding methods based on fast matrix multiplication. In contrast, it is known that for real edge weights the problem can't be solved significantly more quickly than all pairs shortest paths.

"Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time", Glencora Borradaile and Philip N. Klein and Shay Mozes and Yahav Nussbaum and Christian Wulff-Nilsen, arXiv:1105.2228. A planar graph with multiple sources and sinks is almost the same thing as a 2-apex graph with a single vertex (one of the apexes) as source and a single vertex (the other apex) as sink. So the question that comes to mind after seeing this title is: how much harder would it be to handle apex graphs, or k-apex graphs, when the apexes are not the terminals?

"The Graph Minor Algorithm with Parity Conditions", Ken-ichi Kawarabayashi and Bruce Reed and Paul Wollan. There have been previous papers on new faster algorithms for finding graph minors that were announced at conferences and then never seemed to find their way to a full journal version. It's unfortunate, because then there isn't a detailed algorithm one can rely on in one's own papers and there isn't much incentive for others to fill the gap. Let's hope this one (claiming that even with additional constraints on the parity of the contracted paths in the minor the problem can be solved in near-linear time) meets a better fate.

There were even more graph algorithm papers than the ones I list above, so this seems to have been a very good year for the subject. I'm also pleasantly surprised to see some fixed parameter tractability here; lately that seems to have been exiled to the European conferences but I don't think there's any good reason beyond fashion for that. Computational geometry doesn't seem to have done very well at FOCS, but at least there's Larsen's paper there.