(Joint work with Felipe Cucker and Dennis Cheung, City University of Hong Kong.)
\\
\\
Condition numbers are important complexity-theoretic tools to capture
a "distillation" of the input aspects of a computational problem that
determine the running time of algorithms for its solution and the
sensitivity of the computed output. The motivation for our work is the
desire to understand the average case behaviour of linear programming
algorithms for a large class of randomly generated input data in the
computational model of a machine that computes with real numbers. In
this model it is not known whether linear programming is polynomial
time solvable, or so-called "strongly polynomial". Closely related to
linear programming is the problem of either proving non-existence of
or finding an explicit example of a point in a polyhedral cone defined
in terms of certain input data. A natural condition number for this
computational problem was developed by Cheung and Cucker, and we analyse
its distributions under a rather general family of input distributions.
We distinguish random sampling of primal and dual constraints
respectively, two cases that necessitate completely different techniques
of analysis. We derive the exact exponents of the decay rates of the
distribution tails and prove various limit theorems of complexity
theoretic importance. An interesting result is that the existence of
the k-th moment of Cheung-Cucker's condition number depends only very
mildly on the distribution of the input data. Our results also form
the basis for a second paper in which we analyse the distributions of
Renegar's condition number for the randomly generated linear programming
problem.