Conference Agenda

Given a natural number d and a weighted graph G=(V,E), the fundamental problem in Euclidean distance geometry is to determine whether there exists a realization of the graph G in R^d such that distances between pairs of points are equal to the corresponding edge weights. This problem naturally arises in many applications that require recovering locations of objects from the distances between these objects. Usually, measurements of the distances are noisy and there can be missing data. Examples of applications are sensor network localization, molecular conformation, genome reconstruction, robotics and data visualization. Algebraic varieties and semialgebraic sets naturally come up in Euclidean distance geometry, since distances between objects are given by polynomials. Hence questions about uniqueness and finiteness of realizations are often algebraic in nature, whereas realizations are found using semidefinite or nonconvex optimization methods. The goal of this minisymposium is to present theory and applications of Euclidean distance geometry, and connect researchers working in Euclidean distance geometry with applied algebraic geometers.

Consider a framework consisting of fixed length bars attached at flexible joints. The central question in rigidity theory is to determine if the resulting framework is rigid or flexible. The minimally locally rigid graphs in dimension d are the bases of a matroid which can be realized as a linear matroid in joint coordinates associated to the classical "rigidity matrix" or as the algebraic matroid in (squared) distance coordinates associated to the Cayley-Menger variety. In this talk we focus on what the algebraic matroid can tell us about stresses and finite motions. This is joint work with Zvi Rosen, Louis Theran, and Cynthia Vinzant.

A (periodic) bar-and-joint framework is a geometric (periodic) graph whose vertices are mapped to points in R^d (for a fixed dimension d) and its edges to straight-line segments between them. The framework’s configuration space consists in all the placements of the same graph which retain the edge lengths (and the abstract periodicity). We enhance the (periodic) bar-and-joint framework structure to include faces of higher dimensions and study several scenarios that preserve or alter in a controlled manner the dimension of the original configuration space.

In 1997, A. Barvinok gave a probabilistic algorithm to derive a feasible solution of a quadratically (equation) constrained problem from its semidefinite relaxation. We generalize this algorithm to handle matrix (instead of vector) variables and to two-sided inequalities, and derive a heuristic for the distance geometry problem. We showcase its computational performance on a set of instances related to protein conformation.