December 18, 2018

From Dynamics to Complexity
A conference celebrating the work of Mike Shub

May 07-11, 2012
hosted by the Fields Institute

Organizing Committee:
Jean-Pierre Dedieu (University Paul Sabatier)
Teresa Krick (Department of Mathematics, University of Buenos Aires)
Charles Pugh (Department of Mathematics, Chicago University)
Amie Wilkinson (Department of Mathematics, Northwestern University)

Supported by the National Science Foundation


Dennis Amenlunxen
Intrinsic volumes of symmetric cones

What is the probability that the solution of a random semidefinite program has rank r? This 15 year old question may be answered in terms of certain localizations of the intrinsic volumes of the cone of positive semidefinite matrices. We describe this connection and give closed formulas for these quantities. The resulting formulas involve integrals that resemble Mehta's integral, but for which we could not yet find a closed expression (as is known for Mehta's integral). Our results cover the semidefinite cones over the real, complex, and quaternion numbers.

(Joint work with Peter Bürgisser)

Diego Armentano
Smale's Fundamental Theorem of Algebra reconsidered

In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton’s method. In this talk we reconsider this algorithm for homogeneous system of equations. Some interesting problems arise.
There are more open problems than answers, including whether this method gives a solution to Smale's 17th problem. (This is a joint work with Mike Shub).

Saugata Basu
A B-S-S analogue of Valiant: complexity theory of constructible functions and sheaves

In an effort to separate out requirement of ``uniformity'' in the study of P vs NP question, Valiant introduced the non-uniform classes VP and VNP. Unlike in the classical theory, the elements of the classes VP and VNP are not languages but sequences of functions. Valiant's theory leads to an elegant reduction of the question whether VP=VNP to a purely algebraic one -- namely, whether the polynomial given by the permanent of an n x n matrix (with indeterminate entries) can be expressed as the determinant of another (possibly polynomially larger) matrix whose entries are are linear combinations of the entries of the original matrix.

In order to define the complexity class, VNP, of functions given a class of functions VP, one needs to define the notion of a push-forward of functions. The standard technique in mathematics is to define such a push-forward using ``fiber-wise integration''. In the B-S-S model over C or R, this involves the choice of a suitable measure to integrate against. Since integration against most normal measures
(other than finite atomic ones) will not be computable (exactly) in the B-S-S model (as the results will not be algebraic), it becomes a subtle problem to choose the right class of functions and the corresponding push-forward. We propose that the class of constructible functions is particularly suited for this purpose, and we try to develop an analogue of Valiant theory for this class. If time permits I will discuss the generalizations of these ideas to constructible sheaves as well.

Carlos Beltran
A mathematician's foray into signal processing

I will introduce a famous problem - which has been open for a decade - in signal processing theory, as well as a surprisingly simple, complete solution greatly inspired by Mike Shub's thoughts. This is common work with two engineers from the Universidad de Cantabria: Oscar González and Ignacio Santamaría.

Lenore Blum


Peter Burgisser
Condition of convex optimization and spherical intrinsic volumes

Abstract: The analysis of the stability and efficiency of algorithms for convex optimization naturally leads to the study of condition numbers. The Grassmann condition, which is a geometric version of Renegar’s condition, is especially suited for a probabilistic analysis. Such analysis can be performed by relying on techniques from spherical convex geometry and differential geometry. Along this way, we obtain an average analysis of the Grassmann condition number that holds for any regular convex cone.
A closer look prompts the investigation of the spherical counterparts of intrinsic volumes -- a notion thoroughly studied for euclidean spaces, but much less so for spheres, so that many fascinating questions remain. (Joint work with Dennis Amelunxen)

Keith Burns
Ergodicity of the Weil-Petersson geodesic flow

The Weil-Petersson metric is an incomplete Riemannian metric on Teichmueller space with negative sectional curvatures. It is invariant under the action of the mapping class group and projects to a metric with finite volume on moduli space. The techniques of Pesin theory, in particular the work of Katok-Strelcyn, have been applied to show that the geodesic flow for this metric is ergodic.
This is joint work with H.Masur and A.Wilkinson.

Felipe Cucker
The work of Mike Shub in Complexity Theory

We overview the contributions of Mike Shub to the understanding of the complexity of numerical problems and the development of efficient algorithms derived from this understanding.

Sylvain Crovisier
Newhouse phenomenon, homoclinic tangencies and uniformity of extremal bundles

In the early 70's Newhouse has shown that there exists a set of surface diffeomorphisms, generic inside a C^2 open subset, which exhibit infinitely many sinks or sources.
This phenomenon appears close to the set of diffeomorphisms having a homoclinic tangencies.
It also holds in higher dimensions (in any C^r topology, r>=1) in the presence of some kinds of homoclinic tangencies (Palis-Viana, Romero, Bonatti-Diaz).

In a joint work with E. Pujals and M. Sambarino, we now provide a converse for the C^1-topology:
any C^1-generic diffeomorphism which exhibits infinitely many sinks or sources can be approximated by a diffeomorphism with a homoclinic tangency.

Rafael de la Llave
Manifolds on the verge of a regularity breadown

We present numerical experiments with A. Haro and R. Calleja on the break down of normally hyperbolic manifolds supporting an rotation in two different cases:
a) skew products, b) conformally symplectic systems.
In both cases, the phenomenon found is that different exponential bundles collapse even if the exponents remain away from each other. Furthermore, there are very precise scaling relations.
Some rigorous thereorems justifying some of the phenomena or the numerics have been proved by Bjerklov and Saprykina or by us. Further phenomena have been uncovered by Calleja and Figueras.

Jonathan Hauenstein
Certification and applications of solutions to polynomial-exponential systems

Systems of polynomial-exponential equations naturally arise in many applications in mechanical and electrical engineering. This talk will explore using alpha-theory to certify solutions, particularly real solutions, to square systems of polynomial-exponential equations. Examples, including a compliant mechanism and a lithium-ion battery model, will be used to demonstrate the ideas.

Arieh Iserles
Mike Shub and the history of FoCM

Abstract: In this talk I will tell the early history of FoCM, a story in which Mike's contribution is crucial. This will not be a mathematical talk (although I promise to use TeX in my presentation), more a personal story of events, encounters and conversations which ultimately have led to outcomes well beyond our expectations.

Vladim Kaloshin
Arnold Diffusion via Invariant Cylinders and Mather Variational Method
The famous ergodic hypothesis claims that a typical Hamiltonian dynamics on a typical energy surface is ergodic. However, KAM theory disproves this. It establishes a persistent set of positive measure of invariant KAM tori. The (weaker) quasi-ergodic hypothesis, proposed by Ehrenfest and Birkhoff, says that a typical Hamiltonian dynamics on a typical energy surface has a dense orbit. This question is wide open. In early 60th Arnold constructed an example of instabilities for a nearly integrable Hamiltonian of dimension $n>2$ and conjectured that this is a generic phenomenon, nowadays, called Arnold diffusion. In the last two decades a variety of powerful techniques to attack this problem were developed. In particular, Mather discovered a large class of invariant sets and a delicate variational technique to shadow them. In a series of preprints: one joint with P. Bernard, K. Zhang and two with K. Zhang we prove Arnold's conjecture in dimension $n=3$. One of the key ingredients is a construction of a net of normally hyperbolic invariant manifolds.

Pascal Koiran
Progress on the real tau conjecture

According to Shub and Smale's tau conjecture, the number of integer roots of a univariate polynomial should be polynomially bounded in the size of the smallest (constant free) straight-line program computing it. This statement becomes provably false if one counts real roots instead of integer roots. I have proposed a real version of the tau conjecture where the attention is restricted to straight-line programs of a special form: the sums of products of sparse polynomials. This conjecture implies that the permanent polynomial cannot be computed by polynomial-size arithmetic circuits. In this talk, I will present some modest progress towards this conjecture.

Francois Ledrappier
Entropies and rigidities of compact manifolds

We introduce and discuss different growth rates associated to a compact Riemannian manifold. We show some inequalities and discuss the equality cases. Unfortunately, it has nothing to do with the Entropy Conjecture.

Anton Leykin, Georgia Tech
Robust certified homotopy continuation

We develop a rigorous homotopy path following algorithm in the Turing machine model to approximate zeros of systems of polynomial equations. Given a start and target system and the initial approximate zero with coefficients and coordinates in Gaussian integers, an approximate zero with Gaussian integer coordinates is obtained. The total bit complexity is linear in the length of the path in the condition metric, and polynomial in the logarithm of the maximum of the condition number along the path, and in the size of the input. Founded on methods developed by Shub and Smale our robust certification algorithm gives the status of a theorem to results computed by its implementation in Macaulay2.

(Joint work with Carlos Beltran)

Gregorio Malajovich
Condition metric, self-convexity and Smale's 17th problem.

Abstract: I will focus on recent developments about the condition metric in the solution variety for systems of homogeneous polynomial equations. First I will review the basic algebraic-geometric construction of the solution variety and the condition number, and explain what is the condition metric.

Then I will explain how the complexity of path-following can be bounded in terms of the condition-metric of the path. This will suggest a geometric version for Smale's 17-th problem: finding short homotopy paths. As a tentative to understand the condition metric, we studied the linear case: systems of polynomials of degree 1. In this context, the logarithm of the condition number is convex along geodesics. This self-convexity property is conjectured to be true for higher degrees. (This is joint work with Carlos Beltrán, Jean-Pierre Dedieu and Mike Shub).

Klaus Meer
Almost transparent short proofs for NP over the reals

The talk will deal with probabilistically checkable proofs PCPs in the real number model of Blum, Shub, and Smale. A first characterization of class NP_{R} by such PCPs will be given. More precisely, after inroducing the main concepts we show that any problem in NP_{R} can be accepted by a verifier which uses logarithmic amount of randomness and inspects a polylogarithmic number of components in the verification proof.

Maria Jose Pacifico
A toy model for flows with equilibria attached to regular orbits

We shall analyze the $C^\infty$ co-cycle $$f: [0,1]\times [0,1] \backslash \{ 1/2\} \to [0,1]\times [0,1]$$
defined as $$f(x,y)=\left( 2x-\lfloor 2x\rfloor, \, y+ \frac{c}{|x-1/2|}-\left\lfloor y+ \frac{c}{|x-1/2|} \right\rfloor \right),\; c\in \R^+ .$$
We prove that $f$ is topologically mixing and if $c>1/4$ then $f$ is mixing with respect to Lebesgue measure. Furthermore we prove that the speed of mixing is exponential. This co-cycle may be seen as a simplified case of the slipping effect in flows with singularities attached to regular orbits.
This is the case for a Lorenz-like flow on $3$-manifolds.

This is a joint work with R. Markarian and J. Vieitez.

Luis Miguel Pardo
Metric Aspects in Algebraic Geometry (on the Average)

The talk is devoted to exhibit some results on the average values of certain metric quantities related to smooth complete intersections algebraic varieties.

Javier Peña
A primal-dual smooth perceptron-von Neumann algorithm

We propose an elementary algorithm for solving a system of linear inequalities $A\transp y >0$ or its alternative $Ax = 0, \, x\ge 0, \, x\ne 0$. Our algorithm is a smooth version of the perceptron and von Neumann's algorithms. Our algorithm retains the simplicity of these algorithms but has a significantly improved convergence rate. Joint work with CMU graduate student Negar Soheili.

Charles Pugh
Holder foliations, revisited

It's joint work with Mike Shub and Amie Wilkinson. We analyze transverse Holder regularity of some canonical leaf conjugacies and invariant foliations for normally hyperbolic dynamical systems. Our results validate claims made by Damjanovic and Katok, and generalize a result of Ilyashenko and Negut.

Enrique Pujals
The Evolutionary Robustness of Forgiveness and Cooperation

A fundamental problem in evolutionary game theory is to explain how cooperation can emerge in a population of self-interested individuals as typically occurs in the prisoner dilemma. Axelrod attributes the reason of emergence of cooperation to the shadow of the future: the likelihood and importance of future interaction.
Since Axelrod, one approach to test the efficiency or robustness of a strategy and further to derive optimal strategies is the evolutionary dynamics (a processes where individuals with low scores die and those with high scores flourish).

A natural question is which strategies or type of strategies are selected by the dynamics equations; in other words, which are the natural attractors and which type of strategies are uniformly selected independently of the strategy set.

We will show that in the context of the evolutionary dynamics associated to the prisoner dilemma, it is possible to identify strategies with uniform local basin of attraction independent of any initial population (provided that ``the shadow of the future' is relevant and ``mistakes are allowed'). It also proved, as was conjectured by Axelrod, that those strategies are `` nice, retaliating, and forgiving".

Jim Renegar
Optimization, Then and Now

Mike's first research in optimization happened in 1985. Although optimization per se has never been a central focus for Mike, he (and coauthors) continue to make significant contributions at regular intervals. We'll summarize conceptual and theoretical advances made since 1985 in the study of algorithms for convex optimization, emphasizing ideas that dovetail in spirit with Mike's work. We'll also briefly describe related results from a current project nearing completion.

Federico Rodriguez Hertz
The mathematical work of Mike Shub in Dynamics

We will give an account of the mathematical contributions of Mike Shub to the development of the Modern Theory of Dynamical Systems. Mike's work have been an inspiration for the dynamics community and I hope to be able to overview some of his ideas and their outcomes.

Federico Rodriguez Hertz (Second talk)
Arithmeticity and topology for actions of higher rank abelian groups

In a recent work with B. Kalinin and A. Katok we showed that:

Theorem: an ergodic invariant measure by a $\Z^k$ action on a $k+1$ dimensional manifold $M$, $k\geq 2$ with positive entropy and Lyapunov exponents in general position is absolutely continuous with respect to Lesbesgue measure.

The only examples of actions of this type that are known are linear actions on tori and some constructions starting with such linear actions blowing up some finite orbits and following with some gluing procedure or taking some finite quotient.

In a joint work with A. Katok we are able to prove that from a measure theoretic point of view these are the only possible examples. We prove that if an action is as in the Theorem then up to taking finite index subgroup and restricting to some period the action is measurably conjugated to a linear action on an infratorus (i.e. a finite algebraic quotient of a torus). Moreover we can show the measurable conjugacy extends to a continuous map from an open invariant subset $U$ of the manifold $M$ to some open invariant subset $V$ of the torus which is necessarily the complement of a finite set. Moreover $U$ is homeomorphic to $V$.

We get several corollaries from this statement, for instance there are no such actions on spheres, if such an action is Anosov then it is smoothly conjugated to actions by linear automorphisms of the torus.

During the talk we shall describe the examples and we will try to show the ideas of the proof of this result and discuss the corollaries.

Jana Rodriguez Hertz
Partial hyperbolicity and the topology of 3-manifolds

A partially hyperbolic diffeomorphism is one having an invariant splitting of the tangent bundle into 3 directions: one expanding -unstable- direction, one contracting -stable- direction, and one intermediate -center- direction. It is one of the natural generalizations of Anosov diffeomorphisms.
Interestingly, 3-dimensional topology is a crucial ingredient in the study of such systems. Here we survey directions of research and open problems relating these two fields.

Maurice Rojas
Solving a Real Analogue of Smale's 17th Problem

We propose a real analogue of Smale's 17th Problem. Our analogue has two parts, respectively dealing with the average-case complexity of counting real roots and approximating real roots. We then describe an approach, based on amoebae of A-discriminants, toward both parts. Our real refinement of Smale's 17th Problem has interesting connections with fewnomial theory over general local fields. The main result we present is an algorithm solving the counting problem. In particular, when the number of variables and monomial terms is fixed, we can attain polynomial-time complexity. Even in this restricted setting, the best previous algorithms were exponential-time.

Carles Simo, Universitat de Barcelona
A global study of 2D dissipative diffeomorphisms with a homoclinic figure-eight

We consider 2D diffeomorphisms having a dissipative saddle and a figure-eight formed by its manifolds. They are simplified models of phenomena with forcing and dissipation. Under generic perturbations the manifolds can split and undulate. This gives rise to different transversal homoclinic points and to a large set of bifurcations.

It should be emphasized that a main goal is to figure out the global behavior. Not only what happens close to a given bifurcation, but to study which kind of dynamical phenomena appear, in a fundamental domain, which captures all the non-trivial facts.

We will present the main tools to study the bifurcation diagram (topological methods, quadratic and cubic tangencies, return maps, cascades of sinks,...) giving rise to different kinds of attractors.

The analysis is illustrated by the numerical study a model which, despite being simple, has a ``universal'' character. All the phenomena predicted by the theoretical analysis are seen to be realized in the model.

Directions for future work will be outlined.

This is a joint work with S. Gonchenko and A. Vieiro

Mike Todd
Exponential gaps in optimization

We survey a number of areas in optimization where (sub)exponential gaps arise between worst-case bounds and typical behavior, and the theory that has been developed to help explain them.

Andrew Torok
Transitivity of nilpotent extensions of hyperbolic systems

Consider a hyperbolic basic set of a smooth diffeomorphism. We are interested in the transitivity of H\"older skew-extensions with fiber a non-compact connected Lie group.
In the case of compact fibers, the transitive extensions contain an open and dense set. For the non-compact case, we conjectured that this is still true within the set of extensions that avoid the obvious obstructions to transitivity. We will discuss the ``correct'' result for extensions by the Heisenberg group: if the induced extension into its abelinization is transitive, then so is the original extension. The conjecture for Heisenberg groups follows. The results for nilpotent groups involve questions about Diophantine approximations.

This is joint work with Ian Melbourne and Viorel Ni\c{t}ic\u{a}

Cynthia Vinzant
The central curve of a linear program

The central curve of a linear program is an algebraic curve specified by a hyperplane arrangement and a cost vector. This curve is the union of the various central paths for minimizing or maximizing the cost function over any region in this hyperplane arrangement. I will discuss the algebraic properties of this curve and its beautiful global geometry, both of which are controlled by the corresponding matroid and hyperplane arrangement.

Shmuel Weinberger
From Complexity to Geometry: Disordered Solids.

Crystals are classically studied via the crystolagraphic group of their symmetry, and the associated flat tori (with symmetry). More disordered forms of matter require a more complex type of
geometry. Quasicrystals are a more disordered state of matter and have been studied using moduli spaces of aperiodic tilings and a natural dynamical system on them. I shall describe a generalization of this theory (in joint work with Bellisard and Ulgen-Yildirim) to manifolds with bounded geometry that (at the least) unifies these theories with ideas important in the study of nonsimply connected compact manifolds (a.k.a. the Novikov conjecture).

Amie Wilkinson
Around the Pugh-Shub conjectures
I will discuss recent work inspired by the conjectures of Charles Pugh and Mike Shub on the "typical" ergodic behavior of conservative partially hyperbolic dynamical systems.

Yosef Yomdin
Algebraic Geometry and Analysis in study of periodic trajectories of ODE's.

We consider the Abel differential equation (1) $y'=p(x) y^2 + q(x) y^3$. A solution y(x) of (1) is called ``periodic'' on [a,b] if y(a)=y(b). Study of periodic solutions of (1) is closely related to the classical Hilbert 16-th (= Smale 13-th) and Poincare Center-Focus problem. Specifically, the problem of bounding a number of isolated periodic solutions of (1), called Smale-Pugh problem, was intensively studied in recent years.

Algebraic Geometry enters the above problems from the very beginning: it is well known that the condition for all the solutions to be periodic (center) is given by an infinite system of polynomial equations in p,q. The ideal generated by these equations in an appropriate ring (the Bautin ideal) determines local bifurcations of the periodic trajectories as p,q vary.
In recent years two algebraic-analytic structures have been discovered, deeply related to the center equations: Composition Algebra and Generalized Moments. The study of these structures significantly improves our understanding of periodic solutions of (1), and recently a serious progress has been achieved here (in works of F. Pakovich and others).
On the other side, very recently the problem of bounding periodic solutions has been connected with certain new fields in Classical Analysis: Analytic Continuation, Turan-Nazarov inequalities, and Discrete Dynamical Systems. While very recent, these observations promise a new insight in the study of periodic solutions. I plan to give a review of these topics.