Simons Collaboration on Algorithms and Geometry Holds Second Annual Meeting

The Simons Collaboration on Algorithms and Geometry gathered for its second all-day annual meeting at the Simons Foundation on Friday, May 13, 2016. The collaboration’s 13 principal investigators, along with eight postdoctoral researchers and 30 additional guests, attended five talks, including a public Simons Foundation lecture, with breaks for casual discussion throughout the day.

Invited guest speakers Aaron Sidford (Microsoft Research New England), Tali Kaufman (Bar-Ilan University), Robert Young (New York University) and László Babai (University of Chicago) delivered the day’s colloquium-style talks.

Aaron Sidford presented major new results on high-dimensional convex optimization. Algorithms in this area are fundamental, with many powerful uses, and Sidford’s work introduces new geometric and analytic techniques to speed up their running times. Many beautiful ideas go into these speedups, including the introduction of clever barrier functions for interior point methods. Sidford’s work also devises new ways to use convex optimization for combinatorial questions that previously did not seem related to high-dimensional geometric algorithms, leading to running-time improvements for central algorithmic questions.

Tali Kaufman presented a recent breakthrough that answers (positively) a question of Mikhail Gromov’s on the existence of previously unknown combinatorial objects with remarkable (and nonintuitive) properties. Gromov asked if there exist arbitrarily large d-dimensional simplicial complexes of bounded degree that have a topological overlap property: Every continuous mapping of such a complex to R^d must have a point in R^d whose pre-image has large cardinality (proportional to the total number of d-faces). A decade ago, Gromov asked whether such objects exist, and subsequently Gromov, Jacob Fox, Vincent Lafforgue, Assaf Naor and János Pach proved that they exist if the maps are affine on each face rather than arbitrary continuous maps. Kaufman, David Kazhdan and Alexander Lubotzky proved that the desired two-dimensional simplicial complexes exist (allowing for general continuous maps) using an argument that is specific to two dimensions, and now Kaufman has succeeded in proving this for arbitrary dimensions, thus fully resolving Gromov’s question. Significantly, she did so by introducing a new local-global criterion that is sure to have other applications. The resulting combinatorial objects are new tools that will probably also have powerful applications in the future. While some algorithmic applications are already known, the fact that such objects were previously not known to exist means that they will not have “off-the-shelf” applications; rather, the community now needs to revisit many research directions while taking advantage of the new opportunity that Kaufman’s construction provides.

Robert Young presented one of the Simons Collaboration on Algorithms and Geometry’s major achievements to date: joint work with Assaf Naor resolving one of the main questions that were described when the collaboration was conceived. This algorithmic question, which was one of the central open questions in approximation algorithms, arises from the sparsest cut problem, which asks for an efficient algorithm to partition a graph into two pieces so as to minimize the size of their weighted interface, allowing for arbitrary weights (capacities and demands). In the mid-1990s, Michel Goemans and Nati Linial devised an algorithm for this problem that remains the best-known algorithm, but despite intensive efforts, even the top researchers in the area were unable to determine how well this algorithm performs. The new Naor-Young result shows that the Goemans-Linial algorithm must make an error of at least c\sqrt{\log n} on some inputs of size n, which is sharp, thus resolving this long-standing open question. (It is quite remarkable that the performance of a specific and well-studied algorithm took such a long time to understand.) Importantly, this result relies on the proof of a new isoperimetric inequality in the Heisenberg group that is of independent interest to analysis and geometric measure theory, and the proof introduces structural results that will be useful in other contexts. This is a new example of the tight connection between geometry and algorithms.

This year’s annual meeting included a two-hour presentation (with a break in the middle) by László Babai on his recent major breakthrough on algorithms for the graph isomorphism problem. The problem itself is very natural and famous. It asks if two graphs on n vertices are isomorphic to each other (i.e., if they are just re-labelings of the same graph). Babai obtained a fast (but not quite polynomial-time) n^{O (\log n)}-time algorithm for this task, employing many new and difficult innovations in addition to using various tools from the literature (including the classification of finite simple groups).

Following the annual meeting, Sanjeev Arora of Princeton University, a principal investigator in the collaboration, delivered a public Simons Foundation lecture titled “Universality Phenomena in Machine Learning, and Their Applications.” In the talk, he presented his work on model-fitting algorithms for machine learning questions, explaining how these algorithms, which use nonconvex optimization, can be shown to work efficiently for certain generative models.