GOAL Workshop in Paris - May 20 and 21


After the kickoff workshop in Berkeley in May 2015 we are pleased to announce the second GOAL Workshop in Paris. Our discussions will focus on computations in real algebraic geometry and their applications.

If you are interested in giving a talk please send an email to Jean-Charles.Faugere at inria.fr.

Short Description of the Project “Geometry and Optimization with ALgebraic method"

 The goal of this project is to develop algorithms and mathematical tools to solve geometric and optimization problems through algebraic techniques. As a long-term goal, the joint team plans to develop new software to solve these problems more efficiently. These objectives encompass the challenge of identifying instances of these problems that can be solved in polynomial time with respect to the number of solutions and modeling these problems with polynomial equations.The conference will take place at UPMC, 4 place Jussieu 75005, Paris.

Schedule of Talks (May 20-21)

FRIDAY May 20

SATURDAY May 21 (Tower 25-26 / Room 105)

Abstracts of the talks

Bernd Sturmfels - Nearest Points on Toric Varieties -- We determine the Euclidean distance degree of a projective toric variety. This extends the formula of Matsui and Takeuchi for the degree of the $A$-discriminant in terms of Euler obstructions. Our primary goal is the development of reliable algorithmic tools for computing the points on a real toric variety that are closest to a given data point. This is joint work with Martin Helmer.

Tim Römer - Normaliz 3.1.1 -- Normaliz, developed at Osnabrück, is an open source tool that implements algorithms for the computation of lattice points in polyhedra, or, in algebraic terms, diophantine linear systems of equations, congruences and inequalities. We present the newest version of Normaliz, its main tools and discuss examples as an illustration.

Xiaoxian Tang - Computing bounds for equiangular lines in Euclidean spaces -- Determining the maximum number of equiangular lines in a r-dimensional Euclidean vector space is an open problem in combinatorics, frame theory, graph theory, linear algebra and many related areas. So far the exact maximum number is only known for a few small dimensions. In this talk, we compute the upper bound of number of equiangular lines by combing the classical pillar decomposition and the semi-definite programming (SDP) method. Our computational results show an explicit bound, which is strictly less than the well-known Gerzon's bound for the dimensions between 44 and 400. Particularly, when the angles is arccos(1/5) or arccos(1/7), we dramatically improve the known SDP bounds.

Carlos Enrique Amendola Ceron - Learning Gaussian Mixtures via Method of Moments -- We consider the problem of estimating the parameters of a mixture of Gaussian distributions from a sample. Following up on Karl Pearson's 19th century proposed solution by method of moments, we study the polynomial systems associated to the moment equations. Based on joint work with Jean-Charles Faugere and Bernd Sturmfels.

Rainer Sinn -Gaussian graphical models and regularity - In statistics, a Gaussian graphical model encodes conditional independence relationships by a zero pattern in the inverse covariance matrix of the jointly normally distributed random variables. We can encode this zero pattern in a graph. To that graph, we can associate the Stanley-Reisner ideal of its clique complex. As it turns out, the geometry of the Gaussian graphical model, which can be phrased as questions about positive semidefinite matrix completion, are related to regularity properties of the minimal free resolution of the ideal. The main idea behind this unexpected connection is the convex geometry of the cone of sums of squares on the subspace arrangement defined by the Stanley-Reisner ideal and its dual cone.

Kaie Kubjas - The geometry of rank-one tensor completion - The talk would be based on an upcoming paper with Thomas Kahle, Mario Kummer and Zvi Rosen.

Mohab Safey El Din - On algorithms for deciding connectivity queries in semi-algebraic sets - Deciding connectivity queries in semi-algebraic sets is a fundamental problem of effective real algebraic geometry. In 1988, Canny provided the first exponential algorithms running in time (sD)^{O(n^2)} where the input is given by s polynomials of degree D involving n variables. The strategy consists in reducing connectivity queries in arbitrary dimension to connectivity queries on curves ; these curves are called roadmaps. In this talk, we will review some techniques which, under some assumptions, allow to compute roadmaps in time (nD)^{O( n log(n) )} in the case of real algebraic sets. Next, we will discuss the practical impact of these results and review a recent technique to decide connectivity queries on curves. Finally, we will show how these contributions can be used to count the number of connected components of semi-algebraic sets on concrete non-trivial examples. Joint work with E. Schost and I. Bannwarth