Solving hard polynomial systems

Abstracts for the talks

Giles Gardam
University of Münster
Using SAT as a tool for hard polynomial systems
Solutions to equations in group algebras can be found by reduction to (a sequence of) polynomial systems over the field. In general, these systems are heavily overdetermined and if solutions exist, then many variables take the value zero. Modern solvers for Boolean satisfiability (SAT) can be an effective tool for tackling these systems, especially in characteristic 2. I will also explain how they can fit into a toolkit for solving such systems in characteristic 0.

Elisa Gorla
Université de Neuchâtel
The complexity of solving hard polynomial systems: invariants and applications
In this talk I discuss the general problem of estimating the complexity of solving a system of polynomial equations via Groebner bases methods. This question is motivated by post-quantum cryptography, as estimating the security of certain cryptographic schemes requires estimating the complexity of solving an associated system of non-homogeneous multivariate polynomials. This is typically done by computing or bounding from above algebraic invariants associated to the system, such as the first and last fall degree, the Castelnuovo-Mumford regularity, or the degree of regularity of the system. In the talk, I introduce these invariants and compare them to each other. I also present some estimates that were obtained via this approach.

Frank Sottile
Texas A&M University
Two hard polynomial systems from enumerative geometry
I will discuss briefly two problems from enumerative geometry and their formulation as systems of polynomials. One involves Galois groups of Fano problems, and the other a possible relation between Welschinger invariants and the degree of the Wronski map in the real Schubert calculus. These systems appear challenging (or not possible) to solve, which has impeded some recent investigations.


Date and Location

April 03 - 04, 2023
Max Planck Institute for Mathematics in the Sciences
E1 05 (Leibniz-Saal)
Inselstr. 22
04103 Leipzig

Scientific Organizers

Rafael Mohr
TU Kaiserslautern/Sorbonne Université

Kemal Rose
MPI for Mathematics in the Sciences

Administrative Contact

Mirke Olschewski
MPI for Mathematics in the Sciences
29.03.2023, 01:27