#### Special week

*October 9 to 13, 2023*

**Polynomials Systems and Real Geometry**(long course, Monday to Friday), I. Emiris and D. Plaumann**Moment Method in Optimization**(short course, Monday and Tuesday), D. Henrion**General audience presentation**, Wednesday 11th, B. Sturmfels

#### Workshop: Geometry of Polynomial System Solving, Optimization and Topology

**Organizers:** C. D’Andrea, P. Lairez, M. Safey El Din, É. Schost, L. Zhi

*October 16 to 20, 2023*

Polynomial systems encode a wide range of non-linear (but static) phenomena which arise in many applications. Non-linearity makes them non-trivial to handle, both from complexity and reliability viewpoints. Still, because of their importance for key applications e.g. in mechanism design and optimization amongst many others, various algorithmic approaches have been developed. During the last decades, tremendous achievements have been accomplished to design faster algorithms for polynomial system solving, extend their capabilities to tackle topological issues and understand their complexities. For instance, let us mention new families of algorithms to exploit algebraic and geometric properties of polynomial systems and their solution sets such as sparsity or weighted and multi-homogeneity, algorithms for understanding the topology of semi-algebraic sets (Betti numbers, connectivity queries), the raise of sums-of-squares certificates to certify emptiness over the reals of polynomial systems through symbolic-numeric approaches, and last but not least, the stellar solution to 17th Smale problem by Lairez following previous works from Beltrán, Cucker and Pardo.

Many challenges remain to be addressed to pave the way towards high performance polynomial system solvers tackling large scale applications. Topical issues lie in the combination of efficiency and certification, computing exact certificates of emptiness, understanding the geometry of polynomial systems and their solution sets to exploit better their properties algorithmically. This workshop will cover broadly all these topics.

**Invited speakers**

## Christian Eder (Kaiserslautern, Germany) * Recent advances in Gröbner basis algorithms
and geometric applications *

**Abstract**

## Elisenda Feliu (Copenhagen, Denmark) * Positive solutions to polynomial systems and applications to reaction networks *

**Abstract**

## Jon Hauenstein (Notre Dame, USA) * Some advances in numerical algebraic geometry for computing real
solutions*

**Abstract.**
Numerical algebraic geometry provides a collection of algorithms
for computing and analyzing solution sets of polynomial systems. This talk
will discuss new techniques that have been developed in numerical algebraic
geometry for focusing on real solution sets of polynomial systems. Several
applications of these techniques will be presented such as computing smooth
points on algebraic sets, approximate synthesis of mechanisms, and path
planning for output mode switching.

## Martin Helmer (Raleigh, USA) **Conormal Spaces and Whitney Stratifications**

**Abstract.** We describe a new algorithm for computing Whitney
stratifications of complex projective varieties. The main ingredients are
(a) an algebraic criterion, due to Lê and Teissier, which reformulates
Whitney regularity in terms of conormal spaces and maps, and (b) a new
interpretation of this conormal criterion via ideal saturations, which can
be practically implemented on a computer. We show that this algorithm
improves upon the existing state of the art by several orders of magnitude,
even for relatively small input varieties. This is joint work with Vidit
Nanda (Oxford).

## Teresa Krick (Buenos Aires, Argentina) *Title to be announced*

**Abstract**

## Monique Laurent
(Centrum Wiskunde & Informatica (CWI) Amsterdam, and Tilburg University, The Netherlands) * Sums of squares approximations in polynomial optimization: performance analysis and degree bounds *

**Abstract**
Polynomial optimization deals with optimizing a polynomial function over a feasible region
defined by polynomial inequalities, thus modeling a broad range of hard nonlinear nonconvex
optimization problems. Hierarchies of tractable semidefinite relaxations have been introduced
that are based on using sums of squares of polynomials as a ``proxy” for global nonnegativity.
These hierarchies give bounds on the global minimum of the original problem with asymptotic
convergence (under a minor compactness assumption). In this lecture we discuss recent results on
the performance analysis of these hierarchies and related effective degree bounds for dedicated
sums of squares representations of positive polynomials on some classes of compact semi-algebraic
sets (including the hypercube, the sphere or the ball).

## Anton Leykin (Atlanta, USA) *Title to be announced*

**Abstract**

## Zijia Li (Beijing,
China) **Title to be announced**

**Abstract**

## Fatemeh Mohammadi (Leuven, Belgium) *Polynomial systems arising in the formal verification of programs*

** Abstract. **
Multiple classical problems in the formal verification of programs such as
reachability, termination, and template-based synthesis can be reduced to
solving polynomial systems of equations. In this talk, I will describe the
primary objects and these connections. In particular, I will show how the
algebraic and geometric techniques can be applied, enhancing the scalability and
completeness for such problems.

## Marc Moreno Maza (London, Canada) *Title to be announced*

**Abstract**

## Chenqi Mou (Beijing, China) *Chordal Graphs in Triangular Decomposition in Top-Down Style*

**Abstract**
In this talk, I will present the connections between chordal graphs from graph theory
and triangular decomposition in top-down style from symbolic computation, including the
underlying theories, algorithms, and applications in biology. Viewing triangular decomposition in
top-down style as polynomial generalization of Gaussian elimination, we show that all the
polynomial sets, including all the computed triangular sets, appearing in several typical
top-down algorithms for triangular decomposition have associated graphs which are subgraphs of
the chordal graph of the input polynomial set. These theoretical results can be interpreted as
“triangular decomposition in top-down style preserves chordality” and are further used to design
sparse triangular decomposition for polynomial sets which are sparse with respect to their
variables. Sparse triangular decomposition is shown to be more efficient than ordinary one
experimentally, and its application on computing equilibria of biological dynamic systems will
also be reported.

This talk is based on the joint work with Yang Bai, Jiahua Lai, and Wenwen Ju.

## Bernard Mourrain (Inria, Sophia-Antipolis) *Solving by duality*

**Abstract.**
Finding the common roots of a set of polynomial equations is a problem that
appears in many contexts and applications. Standard approaches for solving
this difficult question, such as Grobner bases, border basis, triangular sets,
etc. are based on polynomial reductions but their instability against
numerical approximations can be critical.
In this talk, we will describe a dual approach which focuses on linear
functionals vanishing at the roots.
We will review the properties of Truncated Normal Forms, the connexion with
classical computer algebra approaches and resultants. We will also detail the
dual approach in the context of optimisation problems and for analysing
isolated singularities.
Examples from geometric modeling, robotics and tensor decomposition will
illustrate the numerical behavior of these dual methods.

## Cordian Riener (Tromso,
Norway) **Title to be announced**

**Abstract**

## Ana Romero (La Roja,
Spain) **Title to be announced**

**Abstract**

## Pierre-Jean Spaenlehauer (Nancy, France) *Dimension results for sparse systems homogenized via rational polytopes*

**Abstract.**
A classical method to compute with sparse polynomials is to homogenize them
with respect to Newton polytopes, regarding them as homogeneous elements of
Cartier degrees in the Cox ring of a projective toric variety. In this talk,
we
investigate subvarieties defined by generic polynomial systems in the Cox ring
when the degrees are non-necessarily Cartier, with a view towards identifying
alternative toric homogenizations that are suitable for practical
computations.
Joint work with Matías Bender.

#### Topical day: Computer Vision

*October 23, 2023*

**Organizer:** L. Busé

#### Topical day: Mechanism Design and Computer Algebra

*October 24, 2023*

**Organizer:** J. Schicho