Special week

October 9 to 13, 2023

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

Elisenda Feliu, Title to be announced

Abstract

Martin Helmer, 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).

Anton Leykin, Title to be announced

Abstract

Fatemeh Mohammadi 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.

Bernard Mourrain, Title to be announced

Abstract

Topical day: Computer Vision

October 23, 2023

Organizer: L. Busé

Topical day: Mechanism Design and Computer Algebra

October 24, 2023

Organizer: J. Schicho

Code of Conduct