Invited talks
Monday, December 13, 9:00 ~ 9:40 UTC-3
Rigid Homotopies
Felipe Cucker
City University of Hong Kong, Hong Kong
We describe a probabilistic algorithm that, on input $\varepsilon>0$ and a complex polynomial system $F$ given by black-box evaluation functions, outputs an approximate zero of $F$ , in the sense of Smale, with probability at least $1 - \varepsilon$. When applying this algorithm to $u \cdot F$ , where $u$ is uniformly random in the product of unitary groups, the algorithm performs poly$(n,\delta) \cdot L(F)\cdot (\Gamma(F) \log \Gamma(F)+ \log \log \varepsilon^{-1 })$ operations on average. Here $n$ is the number of variables, $\delta$ the maximum degree, $L(F)$ denotes the evaluation cost of $F$ , and $\Gamma(F)$ reflects an aspect of the numerical condition of $F$. Moreover, we prove that for inputs given by random Gaussian algebraic branching programs of size poly$(n, \delta)$, the algorithm runs on average in time polynomial in $n$ and $\delta$. This result may be seen as an affirmative answer to a refined version of Smale’s 17th question, concerned with systems of structured polynomial equations.
Monday, December 13, 9:50 ~ 10:30 UTC-3
The mean height of the solution set of a system of polynomial equations
Martín Sombra
ICREA and Universitat de Barcelona, Spain
Bernstein’s theorem allows to predict the number of solutions of a system of Laurent polynomial equations in terms of combinatorial invariants. When the coefficients of the system are algebraic numbers, we can ask about the height of these solutions. Based on an on-going project with Roberto Gualdi (Regensburg), I will explain how one can approach this question with tools from Arakelov and toric geometries.
Monday, December 13, 11:00 ~ 11:40 UTC-3
An Algorithm for the Convex Feasibility Problem
Jim Renegar
Cornell University, US
We consider the problem of finding a point in the intersection of a finite collection of closed convex sets. We briefly recall perhaps the most classical of algorithms, so-called projection methods, which are elegant but in general impractical especially in high dimensions, unless the convex sets are very simple such as half-spaces. We present and analyze an elementary algorithm which is similar in spirit to projection methods, but which requires that for each of the convex sets, a point is known in its interior. This algorithm typically does scale nicely to high dimensions, and possesses similar convergence properties to projection methods. (Joint work with Song Zhou.)
Monday, December 13, 11:50 ~ 12:30 UTC-3
Univariate Rational Sum of Squares
Agnes Szanto
North Carolina State University, United States
It is well-known that a non-negative univariate real polynomial is a sum of 2 squares of real polynomials. Landau in 1905 proved that every univariate polynomial with rational coefficients which is strictly positive on R is a sum of 8 squares of rational polynomials. However, for rational polynomials that are non-negative on R, Scheiderer in 2013 constructed examples which are not sums of squares of rational polynomials. In this talk we consider the local case, namely, polynomials that are non-negative on the real roots of another non-zero polynomial. Parrilo in 2003 gave a simple construction that implies that if f in R[x] is squarefree and g in R[x] is non-negative on the real roots of f then g is a sum of squares of real polynomials modulo f. We extend this result to the case when f is an arbitrary rational polynomial and g in Q[x] is non-negative on the real roots of f, assuming that gcd(f/d,d)=1 for d=gcd(f,g). In this case we prove that g is a positive rational combination of squares of rational polynomials modulo f. Joint work with Teresa Krick and Bernard Mourrain.
Monday, December 13, 14:30 ~ 15:10 UTC-3
A Theoretical Computer Science Perspective on Consciousness
Lenore and Manuel Blum
Carnegie Mellon University and UC Berkeley, United States
The quest to understand consciousness, once the purview of philosophers and theologians, is now actively pursued by scientists of many stripes. We examine consciousness from a theoretical computer science (TCS) perspective.
We formally define the Conscious Turing Machine (CTM) and consciousness in the CTM. Explanations of phenomena associated with consciousness are derived from the model and draw confirmation from consistencies, at a high-level, with the cognitive/neuroscience literature.
The CTM is inspired by Turing’s simple yet powerful model of computation and Baars’ Global Workspace Theater model of consciousness, subsequently extended to the Global Neuronal Workspace model by Dehaene and Changeux.
The CTM is not a standard Turing Machine. What gives the CTM its “feeling of consciousness” is not its input-output map, nor its computing power, but rather what's under the hood: its Global Workspace architecture, its predictive dynamics (cycles of prediction, feedback and learning), its rich multi-modal inner language (Brainish) and certain Long Term Memory processors, especially its Inner Speech and Model-of-the-World processors.
We are not looking for a model of the brain but rather for a simple model of consciousness. The reasonableness of the model (and its TCS perspective) should be judged by its contribution to the discussion and understanding of consciousness and related topics.
Monday, December 13, 15:20 ~ 16:00 UTC-3
Three group actions
Gregorio Malajovich
Universidade Federal do Rio de Janeiro, Brasil
A major achievement in the theory of homogeneous polynomial system solving was the solution of Smale's 17th problem. The theory that lead to the formulation of that problem and its solution is based on one group action, the action of the unitary group on the solution variety. This action gives a suitable notion of coordinate invariance.
Unitary action is not available in the more general context of possibly sparse polynomial systems. Instead, I will present two group actions that will play the same role: renormalization, and monomial transforms. Then I will hint how I expect to certify solutions at toric infinity, or near toric infinity.
Tuesday, December 14, 9:00 ~ 9:40 UTC-3
Moment representations, exactness and approximation
Bernard Mourrain
Inria, Université Côte d'Azur, France
How well is a measure characterized by its moments is an old question which appear in many contexts and applications. In polynomial optimization, it is the basis for so-called moment relaxation hierarchies, which allow to compute global optima of polynomial functions on (compact) basic semi-algebraic sets. Computing the optimal moment sequence(s), positive on the quadratic module of the semi-algebraic set, by convex optimization, one can approximate the global solution(s) of the non-linear optimization problem.
In this talk, we will discuss conditions for which this approach gives an exact moment representation of a measure. We will then consider the properties of approximation of moment sequences, give an Effective Putinar Positivstellensatz and present a quantitative analysis of the approximation of measures by positive moment sequences, with new polynomial bounds in the intrinsic parameters of the problem. This presentation is based on a join work with Lorenzo Baldi.
Tuesday, December 14, 9:50 ~ 10:30 UTC-3
Fast approximation on the real line
Arieh Iserles
University of Cambridge, United Kingdom
The original motivation for this work has been spectral methods for dispersive PDEs, whereby the underlying spatial domain is the whole real line. Seeking `good’ orthonormal systems on the real line, Marcus Webb and I have developed an overarching theory relating such systems which, in addition, have a tridiagonal differentiation matrix, to Fourier transforms of appropriately weighed orthogonal polynomials. Thus, for every Borel measure we obtain an orthonormal system in a Paley—Wiener space, which is dense in $L_2(\mathbb{R})$ iff the measure is supported on all of $\mathbb{R}$. In this talk I will introduce this theory, illustrate it by examples (in particular, Hermite and Malmquist—Takenaka functions) and, time allowing, take it in some of the following directions:
- Characterisation of all such orthonormal systems whose first $n$ coefficients can be computed in $O(n \log n)$ operations;
- Sobolev-orthogonal systems of this kind;
- The emerging approximation theory on the real line.
Tuesday, December 14, 11:00 ~ 11:40 UTC-3
Revisiting the definition of stability of algorithms
Carlos Beltrán
Universidad de Cantabria, España
What does it mean that an algorithm is "stable"? Are we sure that the standard definitions (forward, backward, mixed stable) are sound and definitive? If we have two stable algorithms, one eating the output produced by the other, can we assure that the composed algorithm is stable? These appear to be simple questions but they are not. In this talk I will discuss the answers; based on a joint work with Vanni Noferini and Nick Vannieuwenhoven.
Tuesday, December 14, 11:50 ~ 12:30 UTC-3
Some relations between dynamics and computation
Michael Shub
City College and the Graduate Center of CUNY, United States of America
I will discuss joint work on two topics. The first is disease prediction with a maximal entropy model that has some similarity to joint work with Teresa et al some years ago on the distribution of amino acids in cells. The second topic is bifurcation theory in cellular dynamics.
Here we clarify the approach of Rajapakse-Smale via the pitchfork bifurcation, with application to the modeling of metastatic breast cancer and cellular division.
Tuesday, December 14, 14:30 ~ 15:10 UTC-3
Perfect necklaces
Verónica Becher
Universidad de Buenos Aires, Argentina
A word is a finite sequence of symbols in given alphabet and a necklace is the equivalence class of a word under rotations. I will talk about perfect necklaces, nested perfect necklaces, marvelous necklaces and many open questions.
Wednesday, December 15, 9:00 ~ 9:40 UTC-3
On the number of roots of random polynomials
Diego Armentano
Universidad de la República, Uruguay
The study of the roots of random polynomials is an important research area of Mathematics and in some areas of Physics. For almost a century a considerable amount of literature about this problem has emerged from fields as probability, geometry, algebraic geometry, algorithm complexity, quantum physics, etc. In spite of its rich history it is still an extremely active field. In this talk we will review some old and new results on this topic.
Wednesday, December 15, 9:50 ~ 10:30 UTC-3
Sylvester double sums, subresultants and symmetric multivariate Hermite interpolation
Marie-Francoise Roy
IRMAR, Rennes, France, France
(Joint work with Aviva Szpirglas)
Sylvester doubles sums, introduced first by Sylvester are symmetric expressions of the roots of two polynomials. Sylvester's definition of double sums makes no sense in the presence of multiple roots, since the definition involves denominators that vanish when there are multiple roots. The aim of this paper is to give a new definition of Sylvester double sums making sense in the presence of multiple roots, which coincides with the definition by Sylvester in the case of simple roots, to prove that double sums indexed by (k,ℓ) are equal up to a constant if they share the same value for k+ℓ, as well a proof of the relationship between double sums and subresultants, i.e. that they are equal up to a constant. In the simple root case, proofs of these properties are already known. The more general proofs given here are using generalized Vandermonde determinants and symmetric multivariate Hermite interpolation as well as an induction on the length of the remainder sequence of P and Q.
References
d’Andrea, C., Hong, H., Krick, T., and Szanto, A. (2007). An elementary proof of sylvester’s double sums for subresultants. Journal of Symbolic Computation, 42-3.
Roy M.-F. , Szpirglas A. (2020). Sylvester double sums, subresultants and symmetric multivariate Hermite interpolation, Journal of Symbolic Computation,96, pp. 85-107 (preliminary version, arXiv:1805.10609).
Wednesday, December 15, 11:00 ~ 11:40 UTC-3
Krick Subresultants Barcelona
Carlos D'Andrea
Universitat de Barcelona, Spain
Subresultants have been defined to parametrize the Euclidean algorithm to compute the gcd of two univariate polynomials, their properties and generalizations studied since then due to their versatility and applications in polynomial system solving.
In this talk, we will introduce this fascinating topic and illustrate it with some of the contributions made by Teresa Krick and her collaborators in this area.
Wednesday, December 15, 11:50 ~ 12:30 UTC-3
From linear to nonlinear n-width : optimality in reduced modeling
Albert Cohen
Sorbonne Université, France
The concept of n-width has been introduced by Kolmogorov as a way of measuring the size of compact sets in terms of their approximability by linear spaces. From a numerical perspective it may be thought as a benchmark for the performance of algorithms based on linear approximation. In recent years this concept has proved to be highly meaningful in the analysis of reduced modeling strategies for complex physical problems described by parametric PDE's. This lecture will first review two significant results in this area that concern (i) the practical construction of optimal spaces by greedy algorithms and (ii) the preservation of the rate of decay of widths under certain holomorphic transformation. It will then focus on recent attempts to propose non-linear version of n-widths, how these notions relate to metric entropies, and how they could be relevant to practical applications.
Outreach talks
Monday, December 13, 16:30 ~ 17:10 UTC-3
Las Cigarras y los Números Primos
Juan Carlos Pedraza
Ciclo Básico Común - Universidad de Buenos Aires, Argentina
La matemática busca regularidades, patrones que puedan predecir de qué va la cosa. Encontrar la regularidad de un objeto de estudio, encontrar su ritmo, es como amansar un caballo salvaje. Los números primos resultaron ser unos números salvajes que no se han dejado domar, Así, a lo largo del tiempo, fue creciendo uno de los misterios más famosos de la matemática. Será pues, la crónica de un fracaso fascinante. ¿Y las cigarras? Ese es otro misterio.
Tuesday, December 14, 15:20 ~ 16:00 UTC-3
Big data: Cálculo matricial al poder
Liliana Forzani
Universidad Nacional del Litoral, Argentina
Charlaremos sobre Googlear: ¿Cómo hace Google para devolvernos una lista de sitios ante una búsqueda? Dos estudiantes construyeron un algoritmo cuya eficacia los hizo millonarios a ellos y dependientes a todos de su oráculo. El lenguaje del algoritmo son las matrices y su ejecución depende de algunas propiedades específicas del álgebra de matrices.
Las matrices como objetos matemáticos fueron concebidos en el s.XIX y su estructura consolidada a principios del s.XX. La desmesura del tamaño de las matrices cuando se aplican a Big Data exigen operaciones ingeniosamente aplicadas. Solo la historia nos permite entender el presente y entrever el futuro.
Tuesday, December 14, 16:30 ~ 17:10 UTC-3
Teresa… ¿estás ahí?
Adrián Paenza
Universidad de Buenos Aires, Argentina
La huella. La presencia. La empatía. La compañía. Tres anécdotas de las que soy/fui testigo que la definen. Una mujer (más) en el departamento de matemática. ¿Quién te hace mejor y por qué? ¿Quién es docente por naturaleza y cómo se nota? ¿Por qué alguien habría de ser reconocido? El afecto que despierta. Mejorar la calidad de lo que ‘toca’. De eso quiero hablar en “Teresa… ¿estás ahí?”