Abstracts
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
TBA
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.
From
Dynamics to Complexity
