Probabilistic Analysis of Condition Numbers for Linear Programming

In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C _R(A) introduced by Renegar (Ref. 2).     

Modeling Language Evolution

We describe a model for the evolution of the languages used by the agents of a society. Our main result proves convergence of these languages to a common one under certain conditions. A few special cases are elaborated in more depth.     

A Randomized Homotopy for the Hermitian Eigenpair Problem

Foundations of Computational Mathematics - We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an $$n\times n$$ Hermitian matrix $$A$$ , the...     

General formulas for the smoothed analysis of condition numbers

We provide estimates on the volume of tubular neighborhoods around a subvariety Σ of real projective space, intersected with a disk of radius σ. The bounds are in terms of σ, the dimension of the ambient space, and the degree of equations defining Σ. We use these bounds to obtain smoothed analysis estimates for some conic condition numbers. To cite this article: P. Bürgisser et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Fonctions de Nash sur les variétés affines

Sans résuméPartiellement subventioné par C.A.I.C.yT. 2280/83     

Flocking in noisy environments

In recent years, a number of articles proposed mathematical models for emergent phenomena. This is the case, for instance for the flocking of birds or the schooling of fish. In particular, in [F. Cucker, S. Smale, Emergent behavior in flocks, IEEE Trans. on Autom. Control 52 (2007) 852–862], a model was proposed for flocking and it was proved that under certain conditions on the initial positions and velocities of the birds, flocking occurs. In this paper we modify this model by adding random noise to it. We prove that, under conditions similar to those just mentioned, (nearly) flocking occurs in finite time with a certain confidence.     

Exotic Quantifiers, Complexity Classes, and Complete Problems

We define new complexity classes in the Blum–Shub–Smale theory of computation over the reals, in the spirit of the polynomial hierarchy, with the help of infinitesimal and generic quantifiers. Basic topological properties of semialgebraic sets like boundedness, closedness, compactness, as well as the continuity of semialgebraic functions are shown to be complete in these new classes. All attempts to classify the complexity of these problems in terms of the previously studied complexity classes have failed. We also obtain completeness results in the Turing model for the corresponding discrete problems. In this setting, it turns out that infinitesimal and generic quantifiers can be eliminated, so that the relevant complexity classes can be described in terms of the usual quantifiers only.      

On the mathematics of emergence

We describe a setting where convergence to consensus in a population of autonomous agents can be formally addressed and prove some general results establishing conditions under which such convergence occurs. Both continuous and discrete time are considered and a number of particular examples, notably the way in which a population of animals move together, are considered as particular instances of our setting. This article is based on the 1st Takagi Lectures that the second author delivered at Research Institute for Mathematical Sciences, Kyoto University on November 25 and 26, 2006. Steve Smale Partially supported by an NSF grant.     

Solving linear programs with finite precision: I. Condition numbers and random programs

We define a condition number (A,b,c) for a linear program min x s.t. Ax=b,x0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log (A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution. This work has been substantially funded by a grant from the Research Grants Council of the Hong Kong SAR (project number CityU 1085/02P)     

Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets

In [8] counting complexity classes #P_R and #P_C in the Blum-Shub-Smale (BSS) setting of computations over the real and complex numbers, respectively, were introduced. One of the main results of [8] is that the problem to compute the Euler characteristic of a semialgebraic set is complete in the class FP_R^#PR. In this paper, we prove that the corresponding result is true over C, namely that the computation of the Euler characteristic of an affine or projective complex variety is complete in the class FP_C^#PC. We also obtain a corresponding completeness result for the Turing model.