Simons Collaboration on Algorithms and Geometry Annual Meeting 2021

The Simons Collaboration on Algorithms and Geometry (A&G) is an in-house research environment at the Simons Foundation that has been active for the past 7 years. It is devoted to foundational investigations at the interface of mathematical areas such as geometry, analysis, and probability, with the areas of algorithm design and computational complexity in theoretical computer science. The research that is fostered by A&G is focused both on applications and enhancement of the deep synergies between these fields, as well as the development of methodologies and understandings of concepts, basic objects and ideas that occur within these core disciplines even if they are not immediately needed for a certain concrete application. There is also strong interest at A&G in proving impossibility results.

The activities of A&G included 9 group-wide research days per year, ending with an annual conference each May that culminated with a public talk. This year, the A&G annual conference is the closing event of A&G. As such, it will be of a different nature than those of previous years, though it will still end with the usual public talk (delivered this year by PI Braverman; see the enclosed abstract). The rest of the annual conference this year will consist of a director’s review of the entirety of the activities of A&G, followed by two research presentations of the PIs Andoni and Regev (see the enclosed abstracts).

Even though the 9 yearly research days of A&G were its “publicly visible” activities, they constituted a very small part of the activities of A&G. Most of the work at A&G consisted of intensive research efforts in much smaller groups that took place throughout each year. These led to a multitude of results and hundreds of research publications, including many highly visible theorems and breakthroughs on longstanding open questions. It is unrealistic to cover even a tiny fraction of these achievements in the present brief report to the Foundation leadership that accompanies today’s meeting, but a few examples will be mentioned below. Other A&G activities included training aspects. Namely, in addition to its many PIs, A&G supported many postdoctoral researchers, doctoral students, and (long and short term) senior research visitors. This established A&G as a foremost institution for research in the aforementioned directions, and a highly competitive and desirable host of postdoctoral and sabbatical stays. These resulted in many research achievements obtained even by non-PIs through A&G support.

One example of a research achievement at A&G is the development of data structures for the important Approximate Nearest Neighbor Search (ANNS) problem in high-dimensional norms. Despite many efforts over the previous two decades, all such data structures had an approximation that grew like a fixed power of the dimension. Initially, efforts of A&G members led to a geometric conjecture whose positive resolution would have implied that no such data structure exists. That conjecture was that there are expander graphs whose shortest-path metric could be realized faithfully in some low-dimensional norm. After this conjecture was presented, it was proved at A&G that it fails, namely no expander can be realized in low dimensions, which is an impossibility result for dimension reduction. This led to further efforts at A&G that resulted in a construction of a mathematically sophisticated ANNS data structure whose approximation grows slower than any power of the dimension. A core mathematical input here was the theory of nonlinear spectral gaps, which was developed over the years at A&G.

Another example of a research achievement at A&G is the resolution of the intermediate complexity conjecture for approximation versions of Constraint Satisfaction Problems (CSPs). Specifically, (under a standard complexity assumption) we now know that there exist such CSPs whose time complexity grows neither polynomially nor truly exponentially with the number of variables. That CSP is the approximation version of the Unique Games problem (GapUG), whose complexity is the topic of the Unique Games Conjecture (UGC). Progress towards the UGC was achieved at A&G by proving its important variant called the 2-to-2 conjecture through a deep understanding of isoperimetric properties of the Grassmann graph. This enables a translation of all UGC-based hardness results into NP-hardness results at the loss of factor ½.

The third and last example of a research achievement at A&G that we will mention here is the complete understanding of the embeddability properties of Heisenberg groups in Lebesgue spaces. These were based on isoperimetric theorems whose proofs rely on new a structural understanding of surfaces in the Heisenberg group. An unexpected aspect of this is that Heisenberg groups of dimensions 3 and 5 behave markedly differently. Applications include a resolution of decades-old conjectures in approximation algorithms (determination up to lower order factors of the integrality gap of the semidefinite programming relaxation of the Sparsest Cut problem, which is an important graph partitioning problem with many application) and metric geometry (e.g. proof that there exist metric subspaces of Lebesgue spaces with indices on both sides of 2 that cannot be embedded in a Hilbert space).

As we explained above, the research achievements at A&G over the past 7 years are too numerous for us to even attempt trying to discuss a small part of them here. We didn’t mention the proof that linear programming is not easier when the polytope over which one optimizes is fixed and the only parameter of the problem is the target linear functional, or the resolution of the weak Pinsker Conjecture in dynamical systems using new structural information of measures on discrete cubes. The 3 research presentations of the day (by Andoni, Braverman, Regev) will describe other research achievements that were made at A&G; see their abstracts in this handout for more information.

Assaf Naor
Princeton University

Collaboration Update

A director’s overview of the A&G Think Tank over the past 7 years, including administrative, organizational and budgetary aspects, personnel, activities, samples of research achievements, and mysteries/challenges that remain.

Alex Andoni
Columbia University

Approximating Edit Distance in Near-Linear Time

Edit distance is a classic measure of similarity between strings, with applications ranging from computational biology to coding. Computing edit distance is also a classic dynamic programming problem, with a quadratic run-time solution, often taught in the “Intro to Algorithms” classes. Improving this runtime has been a decades-old challenge, now ruled likely-impossible using tools from the modern area of fine-grained complexity.

We will briefly survey recent research that led to an algorithm *approximating* the edit distance in near-linear time, up to a constant factor. This research direction has been reenergized by the breakthrough paper of [Chakraborty, Das, Goldenberg, Koucky, Saks; FOCS’18], who showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time.

Joint work with Negev Shekel Nosatzki (FOCS’20).

Oded Regev
Princeton University

Algorithmic and geometric aspects of lattices

A lattice is defined as the set of all integer combinations of $n$ linearly independent vectors in $\R^n$. These geometrical objects hide a rich structure that has attracted the attention of mathematicians for over a century. In recent years, algorithmic problems on lattices have come to the forefront partly due to the key role they play in modern cryptography. I will describe how investigating these algorithmic problems led us to discover new geometric properties of lattices.

4:45 – 5:00 PM ET Webinar waiting room opens
5:00 – 6:15 PM ET Talk + Q&A

Tiling Space and Making Hard Problems Harder
Mark Braverman, Ph.D.
Professor, Department of Computer Science, Princeton University

A shape can tile space if we can take infinitely many copies of the shape and shift them around to cover every point without overlapping. For example, squares and hexagons can tile a plane, but circles can’t. Questions linger, though. What is the smallest surface area a tile may have? Does the answer change if we require the tiles to be symmetric?

In this lecture, Mark Braverman will discuss the question of minimizing the surface area of tiles, a problem that dates back to the 19th century. The question turns out to have surprising connections to computational complexity theory in the context of combining computationally difficult problems to make them even harder. Braverman will elucidate these connections and present results on the minimum surface area problem.

More information is available at the lecture’s page. Participation is optional; separate registration is required. Further instructions and access to join the webinar will be sent to all registrants upon sign-up.

General Meeting Assistance
Emily Klein
MPS Event Coordinator, Simons Foundation
eklein@simonsfoundation.org
(646) 751-1262