Search

The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in n unknowns in time polynomial, on the average, in the size N of the input system. A partial solution to this problem was given by Carlos Beltr an and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that eciently implements a nonconstructive idea of

The theory of computation is the newest and longest segment of Steve Smale’s mathematical career. It is still evolving and, thus, it is difficult to evaluate and isolate the more important of Smale’s contributions. I think they will be as important as his contributions to differential topology and dynamical systems. He has firmly grounded himself in the mathematics of practical algorithms, Newton’s method, and the simplex method of linear programming, inventing the tools and methodology for their analysis. With the experience gained, he is laying foundations for the theory of computation which have a unifying effect on the diverse subjects of numerical analysis, theoretical computer science, abstract mathematics, and mathematical logic. I will try to capture some of the points in this long-term project. Of course, the best thing to do is to read Smale’s original papers; I have not done justice to any of them.

The work of Steve Smale and his colleagues on average case analysis of algorithms [30, 31] and modeling real computations [3, 32] introduced methods and models not previously used in numerical analysis and complexity theory. In particular, the use of integral geometry to bound the sizes of sets of problems where algorithms “go bad” and the introduction of a model of real computation to clearly formulate complexity questions have inspired a great deal of other work. In this chapter, we will survey past results and open problems in three areas: the probability that a random numerical problem is difficult, the complexity of condition estimation, and the use of regularization to solve ill-posed or ill-conditioned problems; we will define all these terms below.

This large format book is described by the author as a coffee table art book; however, it is much more like a labor of love for Steve Smale. Smale not only describes the early difficulties of trying to publish such a mineral “art” volume, but also his efforts to develop the talent of photographing his own specimens, some of which are published here. You can understand his passion for mineral specimens and the development of this eye-candy book from the fact that he decided to enlist the talents of Jeff Scovil (a renowned mineral photographer) to provide the remainder of the color plate images. In total, there are 101 exquisite mineral color photographs. Beside the magnificent photos, Smale also provides a very valuable discourse on his (and his wife Clara’s) personal collecting criteria. Among the many characteristics he discusses, three elements are paramount: beauty, balance, and economy. Beauty is self evident to him; the specimen should be attractive from all angles and all components (matrix and main crystal) should enhance the …

In the period 1960–1965, geometric mechanics was “in the air.” Some key papers were available, such as Arnold’s work on KAM theory and a little had made it into textbooks, such as Mackey’s book on quantum mechanics and Sternberg’s book on differential geometry. In this period, Steve was working on his dynamical systems program. His survey article (Smale [1967]) contained important remarks on how geometric mechanics (specifically Hamiltonian systems on symplectic manifolds) fits into the larger dynamical systems framework. In 1966 at Princeton, Abraham ran a seminar using a preprint of the survey article and it was through this paper that I first encountered Smale’s work. After he visited the seminar, the importance of what he was doing was obvious; also, it became evident that there was great power in asking simple, penetrating, and sometimes even seemingly naive questions. I should add that in the mathematical physics seminar at Princeton that I also had the good fortune of attending, Eugene Wigner had a remarkably similar aura.

This work gives a mathematical foundation for bifurcation from a stable equilibrium in the genome. We construct idealized dynamics associated with the genome. For this dynamics, we investigate the two main bifurcations from a stable equilibrium. Finally, we give mathematical proofs of existence and points of bifurcation for the repressilator and the toggle gene circuits.

SUMMARYGenome architecture is important in transcriptional regulation and study of its features is a critical part of fully understanding cell identity. Altering cell identity is possible through overexpression of transcription factors (TFs); for example, fibroblasts can be reprogrammed into muscle cells by introducing MYOD1. How TFs dynamically orchestrate genome architecture and transcription as a cell adopts a new identity during reprogramming is not well understood. Here we show that MYOD1-mediated reprogramming of human fibroblasts into the myogenic lineage undergoes a critical transition, which we refer to as a bifurcation point, where cell identity definitively changes. By integrating knowledge of genome-wide dynamical architecture and transcription, we found significant chromatin reorganization prior to transcriptional changes that marked activation of the myogenic program. We also found that the local architectural and transcriptional dynamics of endogenous MYOD1 and MYOG reflected the global genomic bifurcation event. These TFs additionally participate in entrainment of biological rhythms. Understanding the system-level genome dynamics underlying a cell fate decision is a step toward devising more sophisticated reprogramming strategies that could be used in cell therapies.

Significance A basic problem in biology is understanding how information from a single genome gives rise to function in a mature multicellular tissue. Genome dynamics stabilize to give rise to a protein distribution in a given cell type, which in turn gives rise to the identity of a cell. We build a highly idealized mathematical foundation that combines the genome (within cell) and the diffusion (between cell) dynamical forces. The trade-off between these forces gives rise to the emergence of function. We define emergence as the coordinated effect of individual components that establishes an objective not possible for an individual component. Our setting of emergence may further our understanding of normal tissue function and dysfunctional states such as cancer.

I first met Rene at the well-known 1956 meeting on topology in Mexico City. He then came to the University of Chicago, where I was starting my job as instructor for the fall of 1956. He, Suzanne, Clara and I became good friends and saw much of each other for many decades, especially at IHES in Paris. Thom’s encouragement and support were important for me, especially in my first years after my Ph.D. I studied his work in cobordism, singularities of maps, and transversality, gaining many insights. I also enjoyed listening to his provocations, for example his disparaging remarks on complex analysis, 19th century mathematics, and Bourbaki. There was also a stormy side in our relationship. Neither of us could hide the pain that our public conflicts over “catastrophe theory” caused. Rene Thom was a great mathematician, leaving his impact on a wide part of mathematics. I will always treasure my memories of him. Steve Smale

In previous work, with Bartholdi and Schick [1], the authors developed a Hodge–de Rham theory for compact metric spaces, which defined a cohomology of the space at a scale α. Here, in the case of Riemannian manifolds at a small scale, we construct explicit chain maps between the de Rham complex of differential forms and the L2 complex at scale α, which induce isomorphisms on cohomology. We also give estimates that show that on smooth functions, the Laplacian of [1], when appropriately scaled, is a good approximation of the classical Laplacian.

Learning theory studies data structures from samples and aims at understanding unknown function relations behind them. This leads to interesting theoretical problems which can be often attacked with methods from Approximation Theory. This workshop - the second one of this type at the MFO - has concentrated on the following recent topics: Learning of manifolds and the geometry of data; sparsity and dimension reduction; error analysis and algorithmic aspects, including kernel based methods for regres- sion and classification; application of multiscale aspects and of refinement algorithms to learning.

In this paper, we take a topological view of unsupervised learning. From this point of view, clustering may be interpreted as trying to find the number of connected components of any underlying geometrically structured probability distribution in a certain sense that we will make precise. We construct a geometrically structured probability distribution that seems appropriate for modeling data in very high dimensions. A special case of our construction is the mixture of Gaussians where there is Gaussian noise concentrated around a finite set of points (the means). More generally we consider Gaussian noise concentrated around a low dimensional manifold and discuss how to recover the homology of this underlying geometric core from data that do not lie on it. We show that if the variance of the Gaussian noise is small in a certain sense, then the homology can be learned with high confidence by an algorithm that has a weak (linear) dependence on the ambient dimension. Our algorithm has a natural interpretation as a spectral learning algorithm using a combinatorial Laplacian of a suitable data-derived simplicial complex.

Partial differential equations and the Laplacian operator on domains in Euclidean spaces have played a central role in understanding natural phenomena. However, this avenue has been limited in many areas where calculus is obstructed, as in singular spaces, and in function spaces of functions on a space X where X itself is a function space. Examples of the latter occur in vision and quantum field theory. In vision it would be useful to do analysis on the space of images and an image is a function on a patch. Moreover, in analysis and geometry, the Lebesgue measure and its counterpart on manifolds are central. These measures are unavailable in the vision example and even in learning theory in general.

This paper attempts to give an extension of learning theory to a setting where the assumption of i.i.d. data is weakened by keeping the independence but abandoning the identical restriction. We hypothesize that a sequence of examples (xt, yt) in X × Y for t = 1, 2, 3,… is drawn from a probability distribution ρt on X × Y. The marginal probabilities on X are supposed to converge to a limit probability on X. Two main examples for this time process are discussed. The first is a stochastic one which in the special case of a finite space X is defined by a stochastic matrix and more generally by a stochastic kernel. The second is determined by an underlying discrete dynamical system on the space X. Our theoretical treatment requires that this dynamics be hyperbolic (or "Axiom A") which still permits a class of chaotic systems (with Sinai–Ruelle–Bowen attractors). Even in the case of a limit Dirac point probability, one needs the measure theory to be defined using Hölder spaces. Many implications of our work remain unexplored. These include, for example, the relation to Hidden Markov Models, as well as Markov Chain Monte Carlo methods. It seems reasonable that further work should consider the push forward of the process from X × Y by some kind of observable function to a data space.