The Simons Collaboration on Algorithms and Geometry gathered for its first day-long annual meeting at the Simons Foundation on May 15. Thirteen of the collaboration’s principal investigators, with postdoctoral researchers Anand Louis, Aravindan Vijayaraghavan and 45 additional guests, attended five talks, with breaks for casual discussion.
Collaboration principal investigator David Steurer of Cornell University gave one of the day’s talks and four invited guest speakers — Ronen Eldan (Weizmann Institute), Shayan Oveis Gharan (University of Washington), Santosh Vempala (Georgia Institute of Technology) and Julia Chuzhoy (Toyota Technological Institute at Chicago) — delivered the others.
Steurer discussed his recent work on a new method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations. Specifically, he showed that for some combinatorial problems, the polytope of feasible solutions is not the linear image of the feasible region of any polynomial sized SDP.
Shayan Oveis Gharan spoke to the group about his recent result with Nima Anari on the approximability of the classic asymmetric traveling salesman problem. Their new proof uses ideas from spectral graph theory, high-dimensional geometry and an extension of the Kadison-Singer solution by Marcus, Spielman and Srivastava.
Julia Chuzhoy then spoke about compelling advances in the last few years in approximation algorithms for graph routing problems; these advances have implications for other areas such as fixed parameter tractable algorithms.
Ronen Eldan presented results that illustrated the potential of stochastic calculus as a tool for proving inequalities with a geometric nature. He focused on the proofs of two new bounds related to the Gaussian Ornstein-Uhlenbeck convolution operator that relies heavily on the use of Ito calculus.
Santosh Vempala reviewed the progress made in the last quarter-century on computing the volume of a convex body in n-dimensional space, and then presented a new algorithm which improves upon the previous best algorithm from 2003 by a factor of n and bypasses the famous KLS hyperplane conjecture, which had once seemed essential to achieving this complexity.
Following the annual meeting, collaboration principal investigator Amit Singer of Princeton University delivered a Simons Foundation Lecture open to the public, titled Solving the 3-D puzzle of rotation assignment in single particle cryo-electron microscopy. He discussed efficient algorithms and methods for reconstructing 3-D structures from multiple noisy 2-D projections of macromolecules obtained from cryo-electron microscropy (cryo-EM). Single particle cryo-EM is becoming a state-of-the-art high-resolution structural method comparable to X-ray crystallography and NMR for imaging biological macromolecules. The main algorithmic challenge in this work consists of finding the correct orientations of many random 2-D projections so that they may be aligned to accurately reconstruct the 3-D structure.
Collaboration director Assaf Naor says he is pleased with the progress of the collaboration thus far. “The first annual meeting was intended to present some of the most important and exciting recent research on foundational questions at the interface of geometry and mathematical aspects of computer science,” he said. “And we discussed cutting-edge research in these areas. The talks and discussions throughout the day between external experts and members of the collaboration highlighted key achievements, new methods and central challenges that will influence the future research of the collaboration.”
Effective-resistance-reducing flows, spectrally thin trees and asymmetric TSP
Given a k-edge-connected graph G = (V,E), a spanning tree T is α-thin with respect to G, if for any S ⊆ V, |T(S,V–S)| ≤ α · |E(S,V–S)|. The thin tree conjecture asserts that for a sufficiently large k (independent of the size of G), every k-edge-connected graph has a 1/2-thin tree. This conjecture is intimately related to designing approximation algorithms for the asymmetric traveling salesman problem (ATSP).
Based on a joint work with Nima Anari, we show that any k-edge-connected graph has a polyloglog(n)/k-thin spanning tree. This implies that the integrality gap of the natural LP relaxation of ATSP is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n). This is the first significant improvement over the Õ(log n) approximation factor for ATSP. Our proof builds on the method of interlacing polynomials of Marcus, Spielman and Srivastava and employs several tools from spectral theory and high-dimensional geometry.
In a typical routing problem, we are given a graph G and a collection of pairs of vertices ( s1,t1),…,(sk,tk), called demand pairs, that we are interested to route. In order to route a demand pair (si,ti), we need to choose a path in G, connecting si to ti . Our goal is usually to route as many of the demand pairs as possible, while keeping the congestion of the routing — the maximum load on any vertex or an edge of G — as small as possible. This general framework gives rise to a number of basic and widely studied graph-routing problems, which have led to the development of a rich toolkit of algorithmic techniques, as well as structural graph theoretic results. In this talk, we will survey some of the central routing problems, the new and the old techniques used for approximating them, and some connections between approximation algorithms and graph theory arising in the context of graph routing.
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2nδ , for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.
Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX 3-SAT.
Based on joint work with James R. Lee and Prasad Raghavendra.
In this talk, we will try to illustrate the potential of stochastic calculus as a tool for proving inequalities with a geometric nature. We’ll do so by focusing on the proofs of two new bounds related to the Gaussian Ornstein–Uhlenbeck convolution operator that heavily rely on the use of Ito calculus. The first bound is a sharp robust estimate for the Gaussian noise stability inequality of C. Borell (which is, in turn, a generalization of the Gaussian isoperimetric inequality). The second bound concerns with the regularization of L1 functions under the convolution operator and provides an affirmative answer to the Gaussian variant of a 1989 question of Talagrand. Based in part on a joint work with James Lee.
Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes and exponential lower bounds for deterministic algorithms in the oracle model). We begin with a review of the progress made in the quarter-century since Dyer, Frieze and Kannan’s breakthrough n23 algorithm, highlighting algorithmic tools as well as connections to probability and geometry. We then present a new algorithm (based on joint work with Ben Cousins), whose complexity grows as n3 for any well-rounded convex body (any body can be rounded by an affine transformation). This improves the previous best Lo-Ve algorithm from 2003 by a factor of n, and bypasses the famous KLS hyperplane conjecture, which appeared essential to achieving this complexity.
Single particle cryo-electron microscopy (EM) recently joined X-ray crystallography and nuclear magnetic resonance spectroscopy as a high-resolution structural method for biological macromolecules. In single particle cryo-EM, the 3-D structure needs to be determined from many noisy 2-D projection images of individual, ideally identical frozen-hydrated macromolecules whose orientations and positions are random and unknown. We will discuss algorithms for estimating the unknown pose parameters. The main focus will be on algorithms that are based on semidefinite programming relaxations that can be viewed as extensions to existing approximation algorithms to max-cut and unique games, two fundamental problems in theoretical computer science.
Amit Singer is a professor of mathematics and a member of the executive committee of the Program in Applied and Computational Mathematics (PACM) at Princeton University. He joined Princeton as an assistant professor in 2008. From 2005 to 2008 he was a Gibbs Assistant Professor in Applied Mathematics at the Department of Mathematics, Yale University.
Singer received his B.Sc. degree in Physics and Mathematics and his Ph.D. degree in applied mathematics from Tel Aviv University, Israel, in 1997 and 2005, respectively. He was awarded the Moore Investigator in Data-Driven Discovery Award (2014), the Simons Investigator Award (2012), the Presidential Early Career Award for Scientists and Engineers (2010), the Alfred P. Sloan Research Fellowship (2010) and the Haim Nessyahu Prize in Mathematics (2007). His current research in applied mathematics focuses on theoretical and computational aspects of data science, and on developing computational methods for structural biology.