This workshop will explore complexity-theoretic and probabilistic aspects of real number computations, with a focus on numerical equation solving, optimization, and the geometry of solution sets. Topics include condition numbers, random real algebraic systems, and the distribution of points on manifolds. We will also address new directions involving effective o-minimality and positive, hyperbolic and Lorentzian polynomials.
Our workshop naturally connects with Computational Algebraic Geometry, particularly around shared interests in solution structure and symbolic-numeric techniques. There is also strong overlap with Numerical Linear Algebra, especially regarding condition numbers, optimization, and the stability of algorithms. Joint sessions or panels could explore the interplay between algebraic structure, numerical behavior, and computational complexity, enriching discussions across disciplines.
Organizers
Purdue University
Georgia Institute of Technology
SISSA
Speakers
Semi-plenary speakers
Leipzig University
TU Dresden
Invited speakers
Osnabrück University
TU Berlin
University of Konstanz
CUNEF Universidad
CUNEF Universidad
University of Warwick
ENS Lyon
INRIA & Université Paris-Saclay
Georgia Institute of Technology
University of Warwick
Universidade Federal do Rio de Janeiro
ETH Zurich
University of North Carolina at Chapel Hill
TU Wien
UiT The Arctic University of Norway
Texas A&M University
MPI Leipzig
Thursday, 9 July
![[HS 09 – 1st Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/HS09.png){kind=link}
14:00-14:30
Julia Lindberg (Georgia Institute of Technology)
Determining the number of isolated complex solutions of a polynomial system is a fundamental problem in computational algebraic geometry. For sparse systems with specialized, non-generic coefficients this problem is nontrivial. This talk focuses on recent results in this area and presents methods based on the celebrated BKK theorem.
14:30-15:00
Ujué Etayo (CUNEF Universidad)
I will present different strategies for placing points as evenly as possible on the three-dimensional sphere, a problem related to minimizing the interaction energy between points. To do so, I will introduce new random constructions based on the Hopf fibration, a geometric tool that transfers well-distributed points from the ordinary sphere to the three-dimensional sphere. These constructions lead to configurations with very low energy and improve previously known theoretical bounds. Numerical experiments also suggest that one of the proposed methods may perform even better than current proven estimates. Overall, the results provide new ways to understand and generate highly uniform point distributions in higher-dimensional geometry.
15:00-15:30
Chiara Meroni (ETH Zurich)
Directional convexity is a refined notion of convexity in which convexity is required only along specific directions. This concept arises naturally in the theory of multivariate calculus of variations and has intriguing applications in cryptography. However, constructing directional convex hulls remains a highly challenging problem. In the few cases where explicit constructions are known, the resulting hulls exhibit rich algebraic and combinatorial structures, sometimes polyhedral, other times semialgebraic. In this talk, I will review key results and algorithms related to directional convexity and present recent developments from a joint work with Bogdan Raita.
15:30-16:00
Pierre Lairez (INRIA & Université Paris-Saclay)
As a fundamental tool for solving multivariate polynomial systems, homotopy continuation deserves both a complexity theory and efficient implementations. However, these two goals have followed very different paths, to the point that very little is known about the complexity of the certified or heuristic algorithms used in practice. Can we understand practice in theory? A complete answer is still far away. In this talk, we focus on two ingredients that are used in practice but are poorly reflected in the theory: Moore’s criterion for isolating zeros, and predictors.
We will see that Moore’s criterion is qualitatively equivalent to Smale’s α-theorem, but that its implementation in interval arithmetic suffers from overestimation. We will also explain why it is difficult to prove a theoretical benefit from predictors, even though they are key to efficient implementations. In the specific case of interval arithmetic, predictors can compensate for overestimation.
16:00-16:30 Coffee Break
16:30-17:00
Cordian Riener (UiT The Arctic University of Norway)
Computing the Betti numbers of semi-algebraic sets is intractable in general PSPACE-hard already in degree four. Under symmetry the situation improves: for sets defined by symmetric polynomials of fixed degree, the equivariant Betti numbers are computable in polynomial time, but these capture only the invariant part of the homology. In a previous work we had been able to show that it is possible to compute the first Betti numbers efficiently. In this talk we will present an algorithm that computes the full rational homology of such a set as an $S_n$-module in polynomial time for fixed degree. The method recovers the module structure from the trivial-representation multiplicities of signed Young subgroups, computed via a Vandermonde-fiber/branched-cover geometry. (Joint work with Saugata Basu).
17:00-17:30
Martin Lotz (University of Warwick)
We observe that the Kronecker product of tensors is the operation that converts the determinant polynomial into Cayley’s first hyperdeterminant. We apply the Kronecker product to iterated matrix multiplication, which results in the hypercomputant, a VNP-complete and VW[1]-complete polynomial whose hardness we prove via the equivariance of the Kronecker product. The construction works over arbitrary commutative semirings and also for the tensor algebra and the exterior algebra. For the tensor algebra this gives a version of noncommutative VNP, and for polynomials over the nonnegative real numbers this gives a version of monotone VNP, all with the hypercomputant as the complete object. We take a parameterized complexity viewpoint and compare the noncommutative setting and the monotone setting. Using standard techniques we obtain optimal algebraic branching program width lower bounds in both settings, and these are notably not always the same. We also prove the polystability of the hypercomputant and that its isotypic components are characterized by their stabilizer.
17:30-18:00
Christian Ikenmeyer (University of Warwick)
We observe that the Kronecker product of tensors is the operation that converts the determinant polynomial into Cayley’s first hyperdeterminant. We apply the Kronecker product to iterated matrix multiplication, which results in the hypercomputant, a VNP-complete and VW[1]-complete polynomial whose hardness we prove via the equivariance of the Kronecker product. The construction works over arbitrary commutative semirings and also for the tensor algebra and the exterior algebra. For the tensor algebra this gives a version of noncommutative VNP, and for polynomials over the nonnegative real numbers this gives a version of monotone VNP, all with the hypercomputant as the complete object. We take a parameterized complexity viewpoint and compare the noncommutative setting and the monotone setting. Using standard techniques we obtain optimal algebraic branching program width lower bounds in both settings, and these are notably not always the same. We also prove the polystability of the hypercomputant and that its isotypic components are characterized by their stabilizer.
18:00-18:30
Pascal Koiran (ENS Lyon)
We prove a generalization to Jennrich’s uniqueness theorem for tensor decompositions in the undercomplete setting. Our uniqueness theorem is based on an alternative definition of the standard tensor decomposition, which we call matrix-vector decomposition. Moreover, in the same settings in which our uniqueness theorem applies, we also design and analyze an efficient randomized algorithm to compute the unique minimum matrix-vector decomposition (and thus a tensor rank decomposition of minimum rank). As an application of our uniqueness theorem and our efficient algorithm, we show how to compute all matrices of minimum rank (up to scalar multiples) in certain generic vector spaces of matrices. Joint work with Rafael Oliveira.
Friday , 10 July
14:00-14:30
Armin Rainer (TU Wien)
I will discuss sharp regularity and stability results for the roots of parameter-dependent polynomials and the eigenvalues of Hermitian and normal matrices. A central result is that any continuous selection of roots of a $C^{d-1,1}$ curve of monic degree-$d$ polynomials lies in the Sobolev class $W^{1,q}$ for all $q$.
14:30-15:00
Paul Breiding (Osnabrück University)
The typical ranks of real 3×3×5 tensors are 5 and 6. We link the rank probabilities of a 3×3×5 tensor with i.i.d. Gaussian entries to the probability of a random cubic surface in 3-space having real lines. As a consequence, we get a bound on the expected number of real lines on such a surface.
15:00-15:30
Gregorio Malajovich (Universidade Federal do Rio de Janeiro)
The condition of a numerical problem is the rate of variation of the solution with respect to the problem instance. It depends on a choice of the metric structure on the space of problem instances. It also depends on the metric structure on the space of solutions. Stability pertains to the algorithm used to solve the problem. Modern computer represent numbers in floating point and perform arithmetics according to the IEEE-754/854 standards, up to some machine precision EPSILON. A strict definition for stability is, given a problem instance represented in floating point, that the algorithm has to produce an approximate solution, with coordinatewise relative precision EPSILON. The above definition entails a particular choice of the metric structure through variable scaling, aka preconditioning or renormalization. I will explain how homotopy over toric varieties is stable, whereas linear, projective or multiprojective homotopy may fail.
15:30-16:00
Ali Mohammad-Nezhad (University of North Carolina at Chapel Hill)
We extend the classic Morse inequalities to polynomial Morse functions on Whitney stratified semi-algebraic sets. Our main motivation is to understand the complexity of nonlinear optimization problems with respect to the topology of the feasible set, which could be very complicated. In particular under certain regularity conditions, these bounds connect the Betti numbers of the feasible set and the number of central paths in nonlinear optimization, which plays a fundamental role, in theory and practice, for modern interior point methods.
16:00-16:30 Coffee Break
16:30-17:30 semi-plenary talk
Mario Kummer (TU Dresden)
We study the space of Lorentzian polynomials with a given support and show that its topology is determined by a polyhedral object known as the Dressian, enabling effective computation in many cases. We prove that this space can always be compactified to a closed (Euclidean) ball. However, we computationally demonstrate that a compactification proposed by Brändén is, in general, not homeomorphic to a closed ball. Finally, we explore connections between these spaces and certain Grassmannian-type semialgebraic sets. This is joint work with Matt Baker, June Huh, and Oliver Lorscheid.
Saturday, 11 July
14:00-15:00 semi-plenary talk
Lorenzo Baldi (Leipzig University)
We investigate foundational questions in the study of tropicalizations of semialgebraic sets, and more generally of definable sets in a polynomially bounded o-minimal structure. Our motivations come from the study of the complexity of representations of positive polynomials, and from Strassen’s theory of the asymptotic spectrum. We use techniques from model theory and real algebraic geometry to prove the Foundamental Theorem of o-minimal tropical geometry. We discuss initial degenerations and initial preorders, and appy our results to study the geometry of (irrational) toric varieties. Based on a joint work with M. Telek.
15:00-15:30
Maurice Rojas (Texas A&M University)
Consider polynomials f_1,…,f_n in Z[x_1,…,x_n] with generic coefficients in {+-1, …, +-H} and union of exponent vectors A. Assume A has cardinality n+2, lies in {-d,…,d}^n, but does not lie in any affine hyperplane. The fastest current algorithm for counting the real roots of F=(f_1,…,f_n) takes deterministic time (n log(dH))^{O(n)}. Finding start points for fast Newton iteration (even for just the real roots) appears to be even harder. We outline how to push farther and
(A) find a set of rational numbers of total bit size (log(dH))^{O(1)} converging
quadratically to all the real roots (when n=1), and
(B) speed up real root counting to time (n log(dH))^{O(1)} for a large fracion
of inputs.
We obtain A via a new, degenerate family of A-hypergeometric series. We obtain B via a randomized version of Baker’s Theorem, along with some additional probabilistic constructions. This is joint work with Weixun Deng, Grigoris Paouris, and Paul Simanjuntak.
15:30-16:00
Claudia Fevola (CUNEF Universidad)
Solutions of the KP equation admit descriptions in terms of divisors on algebraic curves and points in the Sato Grassmannian. Under degenerations, these objects are replaced by KP solitons, divisors on rational nodal curves, and finite Grassmannians. I will describe the geometry and combinatorics of the tropical theta divisor of a metric graph, and explain how it canonically encodes the matroid and Grassmannian structures underlying associated KP multi-soliton solutions. I will also introduce the Hirota variety, which parametrizes tau functions arising from a nodal curve. The framework naturally specializes to real and positive settings. I will conclude with conjectures characterizing when a nodal curve gives rise to real regular solitons. This is joint ongoing work with Simonetta Abenda, Türku Özlum Çelik, and Yelena Mandelshtam.
16:00-16:30 Coffee Break
16:30-17:00
Sebastian Debus (University of Konstanz)
A real symmetric matrix is called d-locally psd if all of its principal submatrices of size d are psd. In this talk we study their spectral geometry. Blekherman, Dey, Shu and Sun introduced a hyperbolic relaxation of the set of eigenvalues that is tight if and only if d is 1,n-1 or n . Kozhasov proved that the spectral set is not convex for (n,d)=(4,2). We relate the spectral geometry to finding certain optimal point configurations in the plane and polynomial optimization problems on the Grassmannian. Moreover, we prove that a real equiangular tight frame is essentially a barely 2-locally psd matrix and show non-convexity for n \geq 4 and d=2 . Joint work with Jose Acevedo, Greg Blekherman, Seokbin Lee and Cordian Riener.
17:00-17:30
Simon Telen (MPI Leipzig)
I will present a study of cubic surfaces from the perspective of positive geometry. This leads to positive geometries in dimension two (the surface minus its 27 lines), dimension three (its complement in three-space), and dimension four (the moduli space). In each case I will describe canonical forms of regions and the combinatorial rank via tropicalization. This is joint work with Bernd Sturmfels.
17:30-18:00
Peter Bürgisser (TUBerlin)
Are the computational intractability of Hilbert’s Nullstellensatz and the algebraic hardness of the permanent logically equivalent? We prove that the P-NP separation in the Blum-Shub-Smale model over the complex numbers implies the separation of the uniform and constant-free versions of Valiant’s complexity classes: $$ P_C e NP_C \Longrightarrow VP^0(u) e VNP^0(u) $$ Thus the existence of a uniform family of polynomial size, constant-free arithmetic circuits computing the permanent, implies the existence of a uniform family of polynomial size, constant-free algebraic circuits for deciding for given complex polynomials whether they have a common zero complex zero. The proof relies on a recent method developed by Andrews, Garg and Schost, who proved that Hilbert’s Nullstellensatz is in the counting hierarchy. We also discuss attempts to prove the converse of the above implication.
Posters
![[PZ09 – 1st Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/poster_zones_1-stock.png){kind=link}
Nicola Da Ponte
(SISSATrieste)
Definability is the property of a function to be well behaved in the sense of o-minimality. A natural question in this regard is deciding how many functions are definable. In 2010, O. Le Gal proved that being definable is a generic property for smooth functions on the Euclidean space. In a similar fashion, we introduce definability as a generic property for eigenfunctions of the Laplacian on compact manifolds. In particular, we show that the generic smooth metric on an embedded compact manifold gives definable eigenfunctions. In this sense, o-minimality can be used as a tool to study their property. This is a joint work with A. A. Agrachov, A. Lerario and M. Testa.
Pedro R. López-Gómez
(CUNEF Universidad)
Over the past decades, the problem of equidistributing points on compact Riemannian manifolds through the minimization of certain repulsive, pairwise interaction energies has garnered significant interest in the mathematical community. Prominent examples of these energies include the Riesz and logarithmic energies, which have been primarily studied on spheres and projective spaces. A natural generalization of projective spaces is the Grassmann manifold or Grassmannian $\operatorname{Gr}{m,d}$, defined as the set of $m$-dimensional linear subspaces of $\mathbb{R}^d$. While the Grassmann manifold has received considerable attention in fields like information theory and computer vision, little is known about energy minimizers. In this poster, I introduce the problem of minimizing the Riesz and logarithmic energies on the Grassmannian $\operatorname{Gr}{2,4}$ and present, for the first time, upper and lower bounds for the minimal discrete energies on this space.
This is joint work with Ujué Etayo.
David Sawall
(TU Dresden)
A polynomial with real coefficients is called real zero if it has only real zeros along each line through the origin and does not vanish at the origin. The Euclidean closure of the connected component of the non-vanishing set of a real zero polynomial containing the origin is called a rigidly convex set. It turns out that these sets are always convex and generalize spectrahedra. It is not known whether all rigidly convex sets are spectrahedra; this is known as the Generalized Lax Conjecture. We introduce a nested hierarchy of spectrahedra that relaxes a given rigidly convex set. We do this by adapting a spectrahedral relaxation of rigidly convex sets developed by Schweighofer. Furthermore, we use an approximation result due to Fang and Fawzi. Lastly, we prove that if a real zero polynomial has only two variables, this hierarchy of relaxations converges to the rigidly convex set. This work is part of my dissertation at Uni Konstanz under the supervision of Markus Schweighofer.