Session II.3 - Real-Number Complexity
Talks
Thursday, June 15, 14:00 ~ 14:30
New developments on the existential theory of the reals.
Till Miltzow
Utrecht University, Netherlands - This email address is being protected from spambots. You need JavaScript enabled to view it.
In Computational Complexity Theory, we categorize algorithmic problems by their difficulty level. Those levels have names like P, PSPACE, NP, PPAD, #P, ER, and many more. They are usually referred to as complexity classes.
One such class (the existential theory of the reals) is denoted by ER and encapsulates all problems that are equally difficult to feasibility. In feasibility, we want to find an x∈R^n such that p(x)=0. Here, p is a polynomial with integer coefficients. Interestingly, it turns out that many relevant problems in Computer Science are equivalent to this core problem. Examples are geometric packing, training neural networks, or finding Nash Equilibria.
To illustrate the implications let us take the example of packing geometric objects, by rotation and translation. Clearly, this problem can be solved by solving polynomial equations. Recent results state that it is not possible to do so without solving polynomial equations. (Or at least methods that are powerful enough to solve polynomial equations.) This explains at least partially, the lack of algorithmic progress on geometric packing, compared to other algorithmic problems like the traveling salesperson problem. We want to note that practical difficulty might be easier, as real-life instances might have more structure than adversary worst-case examples. Still, complexity classes give an important indication of practical difficulty.
In this talk, we will give highlights on the complexity class ER from the last decade.
Thursday, June 15, 14:30 ~ 15:00
The Wonderful Geometry of the Vandermonde map
Cordian Riener
UiT The Arctic University of Norway, Norway - This email address is being protected from spambots. You need JavaScript enabled to view it.
The Vandermonde map is the polynomial map given by the power-sum polynomials. We study the geometry of the image of the nonnegative orthant under under this map and focus on the limit as the number of variables approaches infinity. We will show, the geometry of this limit is the key to new undecidability results in nonnegativity of symmetric polynomials and deciding validity of trace inequalities in linear algebra.
Joint work with Jose Acevedo (Georgia Institute of Technology, USA), Grigoriy Blekherman (Georgia Institute of Technology, USA) and Sebastian Debus (Otto-von-Guericke-University Magdeburg, Germany).
Thursday, June 15, 15:00 ~ 15:30
Matrix decompositions with Newton's method
Jean-Claude Yakoubsohn
Institut de Mathématiques de Toulouse, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We present a general group-theoretic framework to derive efficient Newton-like iterations for the computation and certificate of various matrix decompositions, assuming that a suitable condition is known. We illustrate the approach on a list of applications, such as LU-decomposition, QR-decomposition, eigen-decomposition, singular value decomposition. This framework generalize the contents of the paper "Newton‑type methods for simultaneous matrix diagonalization" by Rima Khouja,· Bernard Mourrain and Jean‑Claude Yakoubsohn published in Calcolo(2022) 59:38.
Joint work with Joris Van der Hoeven (CNRS,LIX,Ecole Polytechnique,Palaiseau,France).
Thursday, June 15, 15:30 ~ 16:00
Characterisations of good convex cones
Vera Roshchina
UNSW Sydney, Australia - This email address is being protected from spambots. You need JavaScript enabled to view it.
There are many properties of facial structure of convex sets that coincide in a lower-dimensional setting but differ in higher dimensions. This talk will cover several such different properties and their relations, including facial exposure, facial dual completeness (niceness), amenability and projectional exposure. Even though the definitions of these properties have a different nature, they form a neat hierarchy. Based on an example of sufficient and necessary conditions for niceness obtained using lexicographic tangents, an argument can be made about a possibility to explain these different notions and their relations using a unified approach.
Joint work with Bruno Lourenço (The Institute of Statistical Mathematics/SOKENDAI, Japan) and James Saunderson (Monash University, Australia).
Thursday, June 15, 16:30 ~ 17:30
Tensor methods for nonconvex optimization
Coralia Cartis
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
We consider the advantages of having and incorporating higher- (than second-) order derivative information inside regularization frameworks, generating higher-order regularization algorithms that have better complexity, universal properties and can certify higher-order criticality of candidate solutions. Time permitting, we also discuss inexact settings where problem information and smoothness assumptions are weakened, without affecting the algorithms’ complexity. Efficient solution of some higher-order polynomial subproblems will also be discussed.
Joint work with Nick Gould (RAL, UK), Philippe Toint (University of Namur, Belgium) and Kate Wenqi Zhu (University of Oxford).
Thursday, June 15, 17:30 ~ 18:00
Strongly Rayleigh distributions and Applications in Algorithm Design
Shayan Oveis Gharan
University of Washington, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
A multivariate polynomial $p(z_1,\dots,z_n)$ is stable if $p(z_1,\dots,z_n)\neq 0$ whenever $\Im(z_i) \gt 0$ for all $I$. Strongly Rayleigh distributions are probability distributions on Bernoulli random variables whose generating polynomial is stable. They can be seen as a natural generalization of product distributions. It is shown these distributions satisfy the strongest form of negative dependence properties one can consider.
In this talk I will go over basic properties of these distributions, and then I will describe some algorithmic applications.
Friday, June 16, 14:00 ~ 14:30
Geometry and Complexity of Binomial Inequalities in Combinatorics
Greg Blekherman
Georgia Tech, US - This email address is being protected from spambots. You need JavaScript enabled to view it.
Polynomial inequalities between counts of substructures are of central interest in combinatorics. For example, we may be interested in inequalities involving the numbers of bases of a matroid of different ranks, or numbers of certain subgraphs of a graph. Verifying validity of such inequalities for all objects (e.g. all graphs) is often a hard (undecidable) problem. Binomial inequalities are also very important in combinatorics, but they are potentially simpler. In particular, their exponents form a convex cone. This convex cone often has a simple structure, which may lead to better complexity. I will mainly give examples of this phenomenon and state some open problems.
Joint work with Annie Raymond (University of Massachusetts, USA).
Friday, June 16, 14:30 ~ 15:00
The zonoid algebra and random intersections in symmetric spaces
Peter Bürgisser
TU Berlin, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
We assign to a compact symmetric space $M$ a commutative graded algebra, whose elements are certain convex bodies (zonoids) in the exterior algebra of the cotangent space $V$ of $M$. They can be viewed equivalently as measures on the Grassmann manifolds of $V$. This Grassmann zonoid algebra allows to describe the intersection of randomly moved submanifolds of $M$, much like the cohomology algebra of $M$ describes intersections with sign count. Moreover, the link to convexity enforces inequalities in the style of the Alexandrov Fenchel inequality. There is a close connection to the theory of valuations.
Joint work with Paul Breiding (University of Osnabrück), Antonio Lerario (SISSA) and Leo Mathis (University of Frankfurt).
Friday, June 16, 15:00 ~ 15:30
Minimal Euclidean Distance degree of Segre-Veronese varieties
Khazhgali Kozhasov
TU Braunschweig, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
The Euclidean Distance degree $\textrm{EDdeg}_Q(X)$ of an algebraic variety $X$ in an inner product space $(\mathbb{R}^N,Q)$ counts the number of complex critical points of the distance function $x\in X\mapsto Q(v-x,v-x)$ from a generic point $v\in \mathbb{R}^N$ to $X$. Since this invariant of $X$ depends on $Q$, it is a natural problem to find or characterize inner products $Q$ that correspond to the minimal possible $\textrm{EDdeg}_Q(X)$. In my talk I will discuss this question for Segre-Veronese varieties, which consist of rank-1 (partially symmetric) tensors. I will show that with respect to the classical Frobenius product $F(A,B)=\sum_{i=1}^n\sum_{j=1}^m A_{ij}B_{ij}$, the variety $X$ of $n\times m$ rank-1 matrices has smallest $\textrm{EDdeg}_F(X)=\min(n,m)$, whereas $\textrm{EDdeg}_Q(X)$ with respect to a sufficiently general inner product $Q$ on $\mathbb{R}^N=\mathbb{R}^{n\times m}$ is much higher.
Joint work with Alan Muniz (University of Campinas, Brazil), Luca Sodomaco (KTH, Sweden) and Yang Qi (NRIA Saclay–Île-de-France and CMAP, École Polytechnique, France).
Friday, June 16, 15:30 ~ 16:00
On the complexity of sparse polynomial solving.
Gregorio Malajovich
Universidade Federal do Rio de Janeiro, Brazil - This email address is being protected from spambots. You need JavaScript enabled to view it.
Smale's 17-th problem, now solved, asked for an average polynomial time algorithm for finding one root of a random dense polynomial system. The proposed algorithms, as well as all the theoretical framework, rely heavily on the hypotheses of Bézout's Theorem. This theorem states that the number of roots of a `generic' system of $n$ complex polynomials in $n$ variables is the product of the total degrees. `Generic' means Zariski open in the set of systems with a tuple of fixed degrees. A system with vanishing coefficients is not generic. One is induced to homogenize the equations and look for roots in projective space. This suggests a canonical topology and geometry for the space of solutions and a projectively invariant inner product structure in the space of coefficients.
I will report on a program to develop rigorous algorithms for sparse polynomial systems, with reasonable complexity bounds. Sparse polynomials means polynomials that are not constrained to be dense or random. Bernstein's root count in terms of Minkowski's mixed volume is much sharper than Bézout's bound. It assumes polynomial systems with a given support, not necessarily dense. Bernstein's theorem counts the number of roots in a certain toric variety.
Solvoing sparse systems with dense technology is not doable. For instance, a homotopy path between a dense random system and a given sparse sysem is not guaranteed to land on a point of the toric variety. Because the root counts can differ exponentially, that event may be extremely unlikely.
I will bound the cost (number of homotopy steps) of a non-deterministic homotopy between two given sparse systems with the same supports. The cost of this algorithm depends on the supports. For instance, Aleksandrov's mixed area is a quermassintegral that generalizes surface area in the same way that mixed volume generalizes ordinary volume. The facet gap measures, for each 1-cone in the fan and for each support polytope, how close is the supporting hyperplane to the nearest vertex. Once the supports are fixed, the cost can be bounded in terms of two condition numbers of the limiting systems: the renormalized toric condition number and the imbalance of the absolute values of the coefficients.
Friday, June 16, 16:30 ~ 17:00
Complexity in Polynomial Optimization: Asymptotic Convergence, Flat Trucation and Semidefinite Programming
Lorenzo Baldi
Sorbonne University, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
In polynomial optimization, the Lasserre-Parrilo hierarchies are used to compute lower approximations of the global minimum of a polynomial objective funciton f over a basic closed semialgebraic set S. In this talk, we investigate three aspects of the complexity of such problems:
- we present asymptotic convergence rates for the lower approximations of the global minimum, using Lojasiewicz inequalities associated to f and to the description of S;
- we characterize flat truncation, that is used to certify finite convergence, and we describe the relationship with the interpolation degree and the support of finitely generated quadratic modules;
- we propose open research directions connecting polynomial optimization with the complexity of semidefinite programming problems.
Joint work with Bernard Mourrain (INRIA d'Universite Cote d'Azur) and Adam Parusinski (Universite Cote d'Azur).
Friday, June 16, 17:00 ~ 17:30
Superpolynomial lower bounds for circuits of constant depth
Sébastien Tavenas
CNRS, Université Savoie Mont Blanc, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Any multivariate polynomial $P(X_1,...,X_n)$ can be written as a sum of monomials, i.e., a sum of products of variables and constants of the field. The natural size of such an expression is the number of monomials. But, what happens if we add a new level of complexity by considering expressions of the form: sum of products of sums (of variables and constants)? Now it becomes less clear how to show that a given polynomial has no small expression. In this talk we will solve exactly this problem. More precisely, we prove that some explicit polynomials do not have polynomial-sized sum-of-products-of-sums (SPS) representations. We can also obtain similar results for SPSPs, SPSPSs, etc. for all expressions of constant depth. We will see also why this problem can be seen an important step for obtaining lower bounds on the size of algebraic circuits.
Joint work with Nutan Limaye (ITU Copenhagen) and Srikanth Srinivasan (Aarhus University).
Saturday, June 17, 14:00 ~ 14:30
Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
Pierre Lairez
Inria, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
How many operations do we need on average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale's 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound $\text{(input size)}^{1+o(1)}$. This improves upon the previously known $\text{(input size)}^{\frac32 +o(1)}$ bound.
The new algorithm relies on numerical continuation along rigid continuation paths. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on average, we can compute one approximate root of a random Gaussian polynomial system of $n$ equations of degree at most $D$ in $n+1$ homogeneous variables with $O(n^4 D^2)$ continuation steps. This is a significant improvement over previous bounds that prove no better than $\sqrt{2}^{\min(n, D)}$ continuation steps on average.
This talk will also be an introduction to Felipe Cucker's talk in the same session.
Saturday, June 17, 14:30 ~ 15:00
Rigid continuation paths II. structured polynomial systems
Felipe Cucker
City University of Hong Kong, Hong Kong - This email address is being protected from spambots. You need JavaScript enabled to view it.
We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as a blackbox evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity $L$. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with $n$ equations of degree at most $D$ in $n$ variables with only poly$(n,D)L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem.
Joint work with Peter Buergisser (TU Berlin, Germany) and Pierre Lairez (INRIA Saclay, France).
Saturday, June 17, 15:00 ~ 16:00
Optimal transport between algebraic hypersurfaces
Antonio Lerario
SISSA and KTH, Italy and Sweden - This email address is being protected from spambots. You need JavaScript enabled to view it.
Optimal transport is the general problem of moving one distribution of mass to another one as efficiently as possible, typically keeping track of the ambient geometry. In this seminar I will present recent results on the optimal transport problem between algebraic hypersurfaces of the same degree in complex projective space -- integration on an algebraic hypersurface defines a measure on projective space, and all these measures have the same mass if the degree of the hypersurface is fixed. I will discuss how this problem is equivalent to a Riemannian geodesic problem away from the discriminant and connect to the condition number of polynomial system solving.
Joint work with P. Antonini (Università di Lecce) and F. Cavalletti (SISSA).
Saturday, June 17, 16:30 ~ 17:00
On a general Kac-Rice formula for the measure of a level set
Diego Armentano
Universidad de la República, Uruguay - This email address is being protected from spambots. You need JavaScript enabled to view it.
Let $X(\cdot) $ be a random field from $\mathbb{R}^D$ to $\mathbb{R}^d$, $D\geq d$. In this talk we'll first study the level set $X^{-1}( u) $, $u \in \mathbb{R}^d$. In particular we'll give a weak condition for this level set to be rectifiable. Then, we will show how to establish a Kac-Rice formula to compute the $(D-d)$ Hausdorff measure. If time permits, we will conclude with some examples of application.
Joint work with José Rafael León (Universidad de la República, Uruguay) and Jean-Marc Azaïs (Université Paul Sabatier III, France).
Saturday, June 17, 17:00 ~ 17:30
On the Average-Case Complexity of Real Feasibility for Circuit Hypersurfaces
J. Maurice Rojas
Texas A&M University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Deciding whether even a single polynomial equation has a real solution is NP-hard, so it is natural to look for speed-ups. One speed-up comes from sparsity, but the necessary tools involve diophantine approximation, e.g., Baker's Theorem on linear forms in logarithms. Further improvements seem to require randomization,
So we propose a randomized version of Baker's Theorem which appears to be new. As a consequence, we can show that deciding real feasibility for n-variate (n+2)-nomials can be sped up if one averages over exponents. We also discuss some preliminary work on averaging over coefficients.
Joint work with Weixun Deng (Texas A&M University), Alperen Ergur (University of Texas at San Antonio), and Grigoris Paouris (Texas A&M University).
Saturday, June 17, 17:30 ~ 18:00
The condition number in complexity theory
Michael Shub
CUNY, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
The condition number has emerged as a complexity ingredient. We discuss this in the context of decision problems where there is joint work with Gregorio Malajovich and independent work of Felipe Cucker. We also briefly discuss search problems and average complexity as well as some lingering questions.
Posters
A geometric condition number for nonlinear underdetermined systems
Nick Dewaele
KU Leuven, Belgium - This email address is being protected from spambots. You need JavaScript enabled to view it.
The condition number of a system of equations $F(x,p) = 0$ parameterised by $p$ measures the sensitivity of the solution $x$ with respect to small changes in $p$. However, some systems admit infinitely many solutions $x$ for any given value of $p$, in which case the standard condition number is always infinite. This poster presents a generalised condition number (called the least-squares condition number) that is generically finite for many underdetermined systems and measures perturbations to the solution in a least-squares sense relative to some reference solution. The expression of this condition number in terms of the partial derivatives of $F$ relates it to existing work on complexity (Dedieu and Kim, 2002) and on distance to singularity (Dégot, 2001). The theory is applied to common matrix and tensor factorisations.
Joint work with Nick Vannieuwenhoven (KU Leuven, Belgium).
Real-number Computability from the Perspective of Computer Assisted Proofs in Analysis
Małgorzata Moczurad
Jagiellonian University, Poland - This email address is being protected from spambots. You need JavaScript enabled to view it.
We present an interval approach to real-number computations. In some aspects it is similar to existing ones. However, those aspects in which our attitude differs give it several advantages. First, we do not need any oracles; we carry out calculations in a way it is done in real-life practice (e.g. in computer assisted proofs in analysis). Second, the interval point of view allows us to consider various kinds of global information. Apparently, the latter has not been treated in the literature.
Joint work with Piotr Zgliczyński (Jagiellonian University, Poland).
What is the probability that a random symmetric tensor is close to rank-one?
Andrea Rosana
SISSA , Italy - This email address is being protected from spambots. You need JavaScript enabled to view it.
We address the general problem of estimating the probability that a real symmetric tensor is close to rank-one tensors. Using Weyl's tube formula, we turn this question into a differential geometric one involving the study of metric invariants of the real Veronese variety. More precisely, we give an explicit formula for its reach and curvature coefficients with respect to the Bombieri-Weyl metric.
These results are obtained using techniques from Random Matrix theory and an explicit description of the second fundamental form of the Veronese variety in terms of GOE matrices. Our findings give a complete solution to the original problem, and in the case of rational normal curves lead to some novel asymptotic results.
Preprint on Arxiv: https://arxiv.org/abs/2301.05502
Joint work with Alberto Cazzaniga (AREA Science Park, Italy) and Antonio Lerario (SISSA, Italy).
On the analytic Morse-Sard property for the endpoint maps in Carnot groups.
Daniele Tiberio
SISSA, Trieste, Italy - This email address is being protected from spambots. You need JavaScript enabled to view it.
In a subriemannian manifold the endpoint map is defined as the final point of the curve determined by the choice of certain parameters, called controls. The Morse-Sard conjecture states that the set that can be reached using only a specific class of curves (determined by the subriemannian structure) has measure zero. We present recent advances in the case of Carnot groups, among the simplest examples of subriemannian manifolds, where the conjecture is still unsolved. We show how in these geometries the specific structure of the endpoint maps allows to study the Morse-Sard conjecture using techniques from semialgebraic geometry, proving the statement for analytic controls.
Joint work with Antonio Lerario (SISSA, Trieste) and Luca Rizzi (SISSA, Trieste).
Condition-based Bounds on the Number of Real Zeros
Josue Tonelli-Cueto
The University of Texas at San Antonio, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
Unlike in complex algebraic geometry, the number of zeros of a real polynomial system is not always the same. In this poster, we explore a new relationship between the number of real zeros and the condition number of a real polynomial system. Among other things, we show that real polynomial systems with many zeros are ill-conditioned and we obtain probabilistic bounds on the number of real zeros of robust classes of random real polynomial systems. Moreover, our method points out to a new possible family of algorithms in real and complex numerical algebraic geometry where the complexity only depends on the logarithms of the condition number and not the condition number itself.
Joint work with Elias Tsigaridas (Inria Paris & IMJ-PRG, France).