Simons Collaboration on Algorithms and Geometry Holds First Annual Meeting

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.”

Shayan Oveis Gharan, University of Washington

Effective-resistance-reducing flows, spectrally thin trees and asymmetric TSP

View Slides (PDF)

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.

Shayan Oveis Gharan is an assistant professor of computer science and engineering at the University of Washington. He received his Ph.D. from the Department of Management Science and Engineering at Stanford University in 2013. Before joining the University of Washington, he spent one and a half years as a postdoctoral Miller fellow at the University of California, Berkeley, where his host was Umesh Vazirani. His main research includes design and analysis of algorithms, graph theory and applied probability. In the past, he has received several awards for his works on the traveling salesman problem.

Julia Chuzhoy, Toyota Technological Institute at Chicago (TTIC)

Approximation algorithms for graph routing problems

View Slides (PDF)

In a typical routing problem, we are given a graph G and a collection of pairs of vertices ( s₁,t₁),…,(s_k,t_k), called demand pairs, that we are interested to route. In order to route a demand pair (s_i,t_i), we need to choose a path in G, connecting s_i to t_i . 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.

Julia Chuzhoy is an associate professor at the Toyota Technological Institute at Chicago (TTIC). She received her Ph.D. in computer science from the Technion – Israel Institute of Technology in 2004 and spent several years as a postdoc at MIT, University of Pennsylvania and Institute for Advanced Study before joining TTIC in 2007. Her research area is theoretical computer science with the main emphasis on the design and analysis of approximation algorithms for NP-hard problems.

David Steurer, Cornell University

Lower bounds on the size of semidefinite programming relaxations

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 2^nδ , 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.

David Steurer is an assistant professor in the department of computer science at Cornell University. Steurer received his Ph.D. from Princeton University and was a postdoctoral researcher at Microsoft Research New England for two years before joining Cornell University. He is the recipient of the 2010 FOCS Best Paper Award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award and an Alfred P. Sloan Research Fellowship. He investigates the power and limitations of efficient algorithms for optimization problems that are at the heart of computer science and its applications. A focus of his work has been the unique games conjectures whose resolution — no matter in which direction — promises new insights into the capabilities of efficient algorithms. As part of an approach to resolve this conjecture, Steurer studies provable guarantees of the sum-of-squares method, a compelling meta-algorithm that applies to a wide-range of problems and has the potential to unify the design of efficient algorithms for difficult optimization problems.

Ronen Eldan, Weizmann Institute of Science

Interplays between stochastic calculus and geometric inequalities and some new bounds related to the Gaussian convolution operator

View Slides (PDF)

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.

Ronen Eldan received his Ph.D. in pure mathematics from Tel Aviv University in 2012 under the supervision of Bo’az Klartag and Vitali Milman, specializing in high dimensional convex geometry, probability theory and computational geometry. After spending two years as a postdoc in the theory groups at Microsoft Research Redmond and the University of Washington, he has recently joined the mathematics department at the Weizmann Institute of Science. His research mainly involves high-dimensional problems of a probabilistic or geometric nature. In particular, he has recently focused on  finding ways to apply tools from the theory of stochastic calculus to prove geometric results. Some of his favorite problems are the hyperplane conjecture (or slicing problem), the Gaussian correlation conjecture and the Kannan–Lovász–Simonovits conjecture.

Santosh Vempala, Georgia Institute of Technology

Gaussian cooling and randomized volume computation

View Slides (PDF)

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 n²³ 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 n³ 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.

Santosh Vempala is a distinguished professor of computer science at Georgia Tech. His research interests are primarily in algorithms, randomness, high-dimensional geometry and spectral methods. He got his Ph.D. from Carnegie Mellon University in 1997, advised by Avrim Blum, and was in the math department at MIT until 2006 except for a year as a Miller Fellow at the University of California, Berkeley. He has written two books, The Random Projection Method (2004) and Spectral Algorithms (with Ravi Kannan, 2009), and continues to get unreasonably excited when a phenomenon that appears complex from one perspective turns out to be simple from another.

Amit Singer, Princeton University

Solving the 3-D puzzle of rotation assignment in single particle cryo-electron microscopy

View Slides (PDF)

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.