Workshop C6 - Real-Number Complexity

Organizers: Carlos Beltrán (Universidad de Cantabria, Spain) - Saugata Basu (Purdue University, USA) - Mark Braverman (Princeton University, USA)

View workshop abstracts PDF



July 17, 14:30 ~ 14:55 - Room T1

Triangulations of monotone families

Nicolai Vorobjov

University of Bath, UK   -

Let $K \subset {\mathbb R}^n$ be a compact definable set in an o-minimal structure over the reals, e.g., a semi-algebraic or a subanalytic set. A definable family $\{ S_\delta|\> 0< \delta \in {\mathbb R} \}$ of compact subsets of $K$, is called a monotone family if $S_\delta \subset S_\eta$ for all sufficiently small $\delta > \eta >0$. The main result of the talk is that when $\dim K \le 2$ there exists a definable triangulation of $K$ such that for each (open) simplex $\Lambda$ of the triangulation and each small enough $\delta>0$, the intersection $S_\delta \cap \Lambda$ is equivalent to one of the five standard families in the standard simplex (the equivalence relation and a standard family will be formally defined). The set of standard families is in a natural bijective correspondence with the set of all five lex-monotone Boolean functions in two variables. As a consequence, we prove the two-dimensional case of the topological conjecture of Gabrielov and Vorobjov on approximation of definable sets by compact families.

Joint work with Saugata Basu (Purdue University, USA) and Andrei Gabrielov (Purdue University, USA).

View abstract PDF

July 17, 15:00 ~ 15:25 - Room T1

Tight space-noise tradeoffs in computing the ergodic measure

Jon Schneider

Princeton University, United States   -

In this work we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is $\varepsilon$, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision $\delta$ in space polynomial in $\log 1/\varepsilon+\log\log 1/\delta$. We also show that this bound is tight up to polynomial factors.

In the course of showing the above, we prove a result of independent interest in space-bounded computation: that it is possible to exponentiate an $n$ by $n$ matrix to an exponentially large power in space polylogarithmic in $n$.

Joint work with Mark Braverman (Princeton University, USA) and Cristóbal Rojas (Universidad Andres Bello, Chile).

View abstract PDF

July 17, 15:30 ~ 16:20 - Room T1

Descriptive Mathematics and Computer Science with Polynomial Ordinary Differential Equations.

Olivier Bournez

Ecole Polytechnique, FRANCE   -

The purpose of the talk is to present the following fact: If you know what 0, 1, -1 are, as well as an addition and a multiplication, and if you remember what an ordinary differential equation is, then you can (re-)define and program many concepts from Mathematics and Computer Science.

In particular we will present/rediscover descriptive complexity, computability and complexity using polynomial ordinary differential equations only.

A title for this talk could also be "Programming with Ordinary Differential Equations”, as these questions also relate to analog models of computations, and in particular to the 1941 General Purpose Analog Computer of Claude Shannon, and the forgotten art of their programming;

Joint work with Daniel Graça (Universidade do Algarve and Instituto de Telecomunicaçoe) and Amaury Pouly (Ecole Polytechnique and University of Oxford and Max Planck Institute for Software Systems).

View abstract PDF

July 17, 17:00 ~ 17:25 - Room T1

Interactive Proofs over the Reals

Klaus Meer

Brandenburg University of Technology, Cottbus, Germany   -

Interactive proofs provide a powerful tool in complexity theory to verify statements. An almighty prover interacts in several rounds with a verifier to convince the latter of a statement. The verifier usually is a randomized polynomial time machine and should detect erroneous proofs with high probability. Shamir's famous result characterizes the class IP of problems that can be accepted by such interactive proofs as PSPACE or, equivalently, by the class PAR of problems decidable in parallel polynomial time.

We study interactive proofs in the framework of real number complexity theory as introduced by Blum, Shub, and Smale. Since space resources alone are known not to make much sense in real number computations the question arises whether a real version of IP can be similarly characterized by real number complexity classes. We shall derive both an upper and a lower bound for the power of real interactive proofs. In particular, we show that Shamir like techniques can be applied to give interactive protocols for problems that can be solved in real parallel polynomial time.

Joint work with Martijn Baartse (until 2016: Brandenburg University of Technology).

View abstract PDF

July 17, 17:30 ~ 17:55 - Room T1

Probabilistic Schubert Calculus

Antonio Lerario

SISSA, Italy   -

Classical enumerative geometry deals with questions like: “How many lines intersect four lines in general position in three-dimensional space?” The answer to this type of questions is provided by a beautiful, sophisticated machinery, which goes under the name of Schubert calculus. Over the real numbers this classical approach fails—there is no generic number of real solutions, which can already be seen in the basic problem of counting the real solutions to a polynomial equation. Understanding even the possible outcomes for higher dimensional versions of the problem becomes increasingly complicated. In this talk I will discuss how enumerative problems over the reals can be studied in a probabilistic way, by answering questions like: “On average, how many real lines intersect four random lines in three-dimensional space?".

Joint work with Peter Bürgisser (TU Berlin).

View abstract PDF

July 17, 18:00 ~ 18:25 - Room T1

Asymptotic variance of the number of real roots of random polynomial systems

Diego Armentano

Universidad de la República, Uruguay   -

In this talk we study the asymptotic variance, as the degree goes to infinity, of the normalized number of real roots of a square Kostlan-Shub-Smale random polynomial system of any size. Our main tools are the Kac-Rice formula for the second factorial moment of the number of roots and a Hermite expansion of this random variable.

Joint work with J.M. Azaïs (Université de Toulouse, France), F. Dalmao (Universidad de la República, Uruguay) and J.R. León (Universidad Central de Venezuela, Venezuela).

View abstract PDF

July 18, 14:30 ~ 14:55 - Room T1

Weak average-case complexity

Martin Lotz

The University of Manchester, United Kingdom   -

It is a well-established fact that, in practical settings, iterative numerical algorithms typically outperform their theoretical convergence guarantees substantially; examples in optimization and numerical analysis abound. This gap does not disappear in the setting of average-case or smoothed analysis. We present the concept of weak average-case complexity, which is based on the observation that removing an extremely small, "numerically invisible" set from the inputs, is enough to get complexity bounds that are well in line with practical experience. A few applications, interesting relations to random matrix theory, and some probabilistic challenges are presented.

Joint work with Dennis Amelunxen (City University of Hong Kong).

View abstract PDF

July 18, 15:00 ~ 15:25 - Room T1

Computing the homology of real projective sets

Teresa Krick

Universidad de Buenos Aires & CONICET, Argentina   -

We describe and analyze a numerical algorithm for computing the homology of real projective varieties. Its cost depends on the condition of the input as well as on its size: it is singly exponential in the number of variables (the dimension of the ambient space) and polynomial in the condition and the degrees of the defining polynomials. The algorithm relies on a new connection between Smale's $\gamma$ quantity and the injectivity radius of the normal bundle of the variety restricted to the sphere.

Joint work with Felipe Cucker (City University of Hong Kong) and Mike Shub (City University of New York).

View abstract PDF

July 18, 15:30 ~ 15:55 - Room T1

On the Computation of the Homology of Semialgebraic Sets

Felipe Cucker

City University of Hong Kong, Hong Kong   -

The computation of homology groups is one of the problems for which the dawn of the critical points method has not resulted in single exponential time algorithms. Instead, the double exponential time of computing them with CAD is still the best known upper bound. But recent work has found single exponential time algorithms for smooth complex projective varieties and weak exponential time for real projective varieties. This last complexity bound amount to say that, if we endow the space of inputs with a Gaussian probability measure, out of a negligible (i.e., exponentially small) set, the algorithm takes exponential time.

In the talk we describe an extension of the last result to basic semialgebraic sets.

Joint work with Peter Buergisser (TU Berlin) and Pierre Lairez (INRIA Saclay).

View abstract PDF

July 18, 16:00 ~ 16:25 - Room T1

On the complexity of sparse polynomial solving.

Gregorio Malajovich

Universidade Federal do Rio de Janeiro, Brasil   -

I shall report on the algorithmic cost of solving sparse polynomial systems by homotopy algorithms. This cost depends on a sparse condition number, which measures how the solutions change in terms of the coefficients. For this analysis to capture the main features of sparseness, the roots have to be considered as elements of a certain toric variety.

Smale's 17-th problem asked about the existence of a polynomial time algorithm for finding one root of a random dense system. One of the main tools in the solution of this problem was invariance through the unitary group action. This tool is not available any more, so other group actions had to be introduced.

View abstract PDF

July 18, 17:00 ~ 17:25 - Room T1

Improved bounds for equivariant Betti numbers of symmetric semi-algebraic sets

Cordian Riener

University of Konstanz, Germany   -

Let $R$ be a real closed field and $S\subset R^k$ be a semi-algebraic set defined by symmetric polynomials whose degree is $d$. The quantitative study of the equivariant rational cohomology groups of such symmetric semi-algebraic sets was initiated recently and it was shown that in sharp contrast to the ordinary Betti numbers, the equivariant Betti numbers can be bounded by quantity that is polynomial in the number of variables $k$. These results were obtained using arguments from equivariant Morse-theory. In this talk we present a different method which improves these previous results. In particular, we show that the equivariant cohomology groups vanish in dimension $d$ and larger and give new bounds on the equivariant Betti numbers for this setup. More importantly, this new approach yields an algorithms with polynomially bounded (in $k$) complexity for computing these equivariant Betti numbers. This is in sharp contrast to the situation of a general semi-algebraic set, where not even an algorithm with a single exponential complexity is not known for computing all the Betti numbers.

Joint work with Saugata Basu (Purdue University, USA).

View abstract PDF

July 18, 17:30 ~ 17:55 - Room T1

Numerical approximation of multiple isolated roots of analytic systems

Jean-Claude Yakoubsohn

Institut de Mathématiques de Toulouse, France   -

It is classical that the convergence of the Newton's method at the neighborhood of a singular isolated root of a system of equations is no longer quadratic. It may even diverge. To fix this problem we propose a new operator, named singular Newton operator, generalizing the classical Newton operator defined in the regular case.

To do so we construct a finite sequence of equivalent systems named \emph{deflation sequence}, where the multiplicity of the root drops strictly between two successive elements of the sequence. Hence the root is a regular root for the last system. Then there exits a regular square system extracted of this one named \emph{deflated system}. The singular Newton operator is defined as the classical Newton operator associated to this deflated system.

The main idea is the following: since the Jacobian matrix is rank deficient at the root, there exists relation between the lines (respectively columns) of this Jacobian matrix. These relations are given by the Schur complement of the Jacobian matrix. When the elements of the Schur complement are added to the initial system, we obtain an equivalent system where the multiplicity of the root has dropped. We call this operation \emph{kerneling}. In this way, a sequence of equivalent system can be defined iteratively.

Finally we perform a local $\alpha$-theory of Smale of this singular Newton operator, which achieves the numerical study.

Joint work with Marc Giusti (\'Ecole Polytechnique, France).

View abstract PDF

July 18, 18:00 ~ 18:25 - Room T1

Quantitative equidistribution of Galois orbits of points of small height on the $N$-dimensional algebraic torus

Marta Narváez-Clauss

University of Barcelona, Spain   -

Bilu's equidistribution theorem establishes that, given a strict sequence of points on the $N$-dimensional algebraic torus whose Weil height tends to zero, the Galois orbits of the points are equidistributed with respect to the Haar probability measure of the compact subtorus, $(S^1)^N$. For the case of dimension one, quantitative versions of this result were independently obtained by Petsche and by Favre and Rivera-Letelier.

We present a quantitative version of Bilu's result for the case of any dimension. Our result gives, for a given point, an explicit bound for the discrepancy between its Galois orbit and the uniform distribution on the compact subtorus, in terms of the height and the generalized degree of the point.

As a corollary of our quantitative version for the case of dimension $N$, we give an estimate for the distribution of the solutions of a system of Laurent polynomials with rational coefficients in terms of the size of the coefficients of the polynomials and their degrees.

Joint work with Carlos D'Andrea (Universitat de Barcelona, Spain) and Martín Sombra (Universitat de Barcelona, Spain).

View abstract PDF

July 19, 14:30 ~ 14:55 - Room T1

The condition number of join decompositions

Paul Breiding

TU Berlin, Germany   -

Joins of real manifolds appear in a wide area of application and often one is interested in decomposing a point on a join into its factors. Naturally, one may expect that the performance of any numerical algorithm that solves the join decomposition problem is governed by the condition number of the problem. In this talk I will define the condition number of the join decomposition problem and describe it as the inverse distance to some ill-posed set in a product of Grassmannians. Moreover, I will model the join decomposition problem as an optimization problem, provide a Newton-like algorithm for it and explain how the condition number influences the performance of this algorithm. Finally, I will show you the behaviour of the condition number close to boundary points of the join.

Joint work with Nick Vannieuwenhoven (KU Leuven, Belgium).

View abstract PDF

July 19, 15:00 ~ 15:25 - Room T1

Small designs on compact algebraic manifolds

Jordi Marzo

Universitat de Barcelona, Spain   -

Let $M$ be a compact smooth real algebraic manifold \[ M=\{ x\in \mathbb{R}^n \;:\; P_1(x)=\dots = P_k(x)=0 \}, \] defined by polynomials $P_1(x),\dots, P_k(x)\in \mathbb{R}[x],$ and let $\mu$ be the Lebesgue measure. A collection of points $x_1\dots, x_N\in M$ is a $t$-design (called also averaging set) if \[ \frac{1}{N} \sum_{i= 1}^N P(x_i)=\frac{1}{\mu(M)} \int_M P(x)\, d\mu(x), \] for all polynomials $P(x)$ of total degree at most $t.$

We show the existence of $t$-designs with a number of points comparable to the dimension of the space of polynomials of degree at most $t$ restricted to $M.$ This generalizes results on the sphere by Bondarenko, Radchenko and Viazovska (2013). Of particular interest is the case of the Grassmanians where our results improve the bounds that had been proved previously.

Joint work with Ujué Etayo (Universidad de Cantabria, Spain) and Joaquim Ortega-Cerdà (Universitat de Barcelona, Spain).

View abstract PDF

July 19, 15:30 ~ 16:20 - Room T1

Amortized complexity bounds for polynomial with algebraic coefficients and application to curve topology

Marie-Francoise Roy

Universite de Rennes 1, France   -

Let $P \in \mathbb{Z} [X, Y]$ be a square-free polynomial of total degree $d$ and coefficients of bitsize $\tau$, and $\mathcal{C} (P) =\{ (\alpha, \beta) \in \mathbb{R}^2 , P (\alpha, \beta) = 0 \}$ be the real algebraic curve defined by $P$. One of our main results is an algorithm for the computation of the local topology in a neighbourhood of each of the singular points and critical points of the projection wrt the $X$-axis in $\tilde{O} (d^5 \tau+d^6)$ bit operations where $\tilde{O}$ means that we ignore logarithmic factors in $d$ and $\tau$. Compared to state of the art sub-algorithms used for computing a Cylindrical Algebraic Decomposition, this result avoids entirely a generic shear. It gives a deterministic algorithm for the computation of the topology of $\mathcal{C} (P)$ $i.e$ a straight-line planar graph isotopic to $\mathcal{C} (P)$ inside $\mathbb{R}^2$ in $\tilde{O} (d^5 \tau + d^6)$ bit operations.

This result can be seen as an application of new amortized complexity bounds for polynomial with algebraic coefficients that we prove in a first part of our work.

Joint work with Daouda Niang Diatta (Université de Ziguinchor, Senegal), Seny Diatta (Université de Ziguinchor, Senegal), Fabrice Rouillier (INRIA, France) and Michael Sagraloff (Max-Planck-Institut für Informatik, Germany).

View abstract PDF

July 19, 17:00 ~ 17:25 - Room T1

A truly universal polynomial differential equation

Amaury Pouly

MPI-SWS, Germany   -

Lee A. Rubel proved in 1981 that there exists a universal fourth-order algebraic differential equation and provided an explicit example: $$ 3 {y ^{'} } ^4 y ^{{''}} {y^{''}}^2 - 4 {y^{'}} ^4 {y ^{''}}^2 y ^{{''}} + 6 {y^{'}}^3 {y^{''}}^2 y^{''} y^{''} +24 {y^{'}}^2 {y^{''}}^4 y^{''} - 12 {y^{'}}^3 y^{''} {y^{''}}^3 -29 {y^{'}}^2 {y^{''}}^3 {y^{''}}^2 +12 {y^{''}}^7 = 0.\quad (1) $$ It is universal in the sense that for any continuous function $f:\mathbb{R}\rightarrow\mathbb{R}$ and any continuous positive function $\varepsilon:\mathbb{R}\rightarrow(0;+\infty)$, there exists a $C^\infty$ solution $y:\mathbb{R}\rightarrow\mathbb{R}$ to (1) such that $|f(t)-y(t)|<\varepsilon(t)$ for all $t\in\mathbb{R}$. In other words, there is always a solution of (1) that is $\varepsilon$-close to $f$ everywhere. However this result suffers from a big shortcoming, identified as an open question by Rubel in his paper:

``It is open whether we can require that the solution that approximates $f$ be the unique solution for its initial data.''

Indeed, the solution to (1) is not unique when ones adds the condition that $y(0)=y_0$ for example. In fact, one can add a countable number of such conditions and still not get uniqueness of the solution. This is not surprising because the construction of Rubel fundamentally relies on the non-uniqueness of the solution to work.

Our main result is to answer Rubel's question positively. More precisely, we show that there a polynomial $P$ of degree $k$ such that for any continuous function $f:\mathbb{R}\rightarrow\mathbb{R}$ and any continuous positive function $\varepsilon:\mathbb{R}\rightarrow(0;+\infty)$, there exists $y_0,y_0',\ldots,y_0^{(k-1)}\in\mathbb{R}$ such that the unique analytic solution $y$ to $P(y,y',\ldots,y^{(k)})=0$ and $y(0)=y_0$, $y'(0)=y_0'$, ..., $y^{(k-1)}(0)=y_0^{(k-1)}$ is such that $|f(t)-y(t)|<\varepsilon(t)$ for all $t\in\mathbb{R}$. The major difference with Rubel's result is that we get unicity by requiring that the solution be analytic. This requires a completely different and more involved construction. A by-product of the proof is that $y_0$ is constructive and in fact computable from $f$ and $\varepsilon$.

Joint work with Olivier Bournez (LIX, Ecole Polytechnique, France).

View abstract PDF

July 19, 17:30 ~ 17:55 - Room T1

An update on the $fg+1$ problem for Newton polygons

Pascal Koiran

Ecole Normale Supérieure de Lyon, France   -

Let $f$, $g$ be bivariate polynomials with at most $t$ monomials each. The product $fg$ can have up to $t^2$ monomials, but only $2t$ of them can appear as vertices of the Newton polygon of $fg$. If we add a constant (say, the constant 1) to this product, the determination of the maximum number of vertices of the corresponding Newton polygon becomes quite difficult. This is due to possible cancellations with the constant term of $fg$ (which may expose some monomials from the interior of the Newton polygon of $fg$).

This problem is motivated by a connection to an algebraic version of the P versus NP problem, as explained in my paper on the "tau-conjecture for Newton polygons" (joint work with Natacha Portier, Sébastien Tavenas and Stéphan Thomassé).

In this talk I will present some connections with problems from combinatorial geometry, and some results obtained by William Aufort for his Master's degree. His internship report is available at:

View abstract PDF



Geodesics in the Condition Metric and Curvature

Juan G. Criado del Rey

Universidad de Cantabria, España   -

Given a Riemannian manifold $(\mathcal{M},g)$ and a smooth submanifold $\mathcal{N}$, the condition metric is the metric in $\mathcal{M}\setminus\mathcal{N}$ given by $g_\kappa(x) = d(x,\mathcal{N})^{-2}g(x)$, where $d(\cdot,\mathcal{N})$ is the distance function to $\mathcal{N}$. A question about the behaviour of the geodesics in the condition metric arises from the works of Beltrán, Dedieu, Malajovich and Shub: is it true that for every geodesic segment in the condition metric the closest point to $\mathcal{N}$ is one of its endpoints? Previous works show that, under some smoothness hypotheses, the answer to this question is positive when $\mathcal{M}$ is the Euclidean space $\mathbb{R}^n$. We extend this result by proving that the answer is also positive when $\mathcal{M}$ has non-negative sectional curvatures. We also prove that this property fails if there is some point in $\mathcal{M}$ with negative sectional curvatures.

View abstract PDF

On the number of tangents to hypersurfaces in $\mathbb{R}P^n$ in random position

Khazhgali Kozhasov

SISSA, Italy   -

Given $2n-2$ smooth hypersurfaces $X_1,\dots, X_{2n-2}$ in $\mathbb{R}P^n$ we are interested in the average number $T(X_1,\dots,X_{2n-2})$ of projective lines simultaneously tangent to $g_1X_1,\dots,g_{2n-2}X_{2n-2}$, where $g_1,\dots,g_{2n-2}$ are independent and uniformly distributed $O(n+1)$-transformations.

We express $T(X_1,\dots,X_{2n-2})$ in terms of the expected degree of the grassmanian $Gr(2,n+1)$ (introduced recently by P. Burgisser and A. Lerario) and some curvature integrals of $X_1,\dots,X_{2n-2}$.

For example, when $n=3$ and all $X_1,\dots,X_4$ are spheres (in the metric of $\mathbb{R}P^3$) of radius $r\in (0,\frac{\pi}{2})$ we have

$$ T(X_1,\dots,X_4) \approx 1.72 \left( \frac{8}{\pi} \sin r \cos r \right)^4$$

Joint work with Antonio Lerario (SISSA).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.