**Gregorio Malajovich and Mike Shub**:
A theory of NP-completeness and ill-conditionning for approximate real computations .
(March 2017).

**ABSTRACT: **
We develop a complexity theory for approximate real com-
putations. We first produce a theory for exact computations but with
condition numbers. The input size depends on a condition number,
which is not assumed known by the machine. The theory admits deter-
ministic and nondeterministic polynomial time recognizable problems.
We prove that P is not NP in this theory if and only if P is not NP in
the BSS theory over the reals.

Then we develop a theory with weak and strong approximate compu- tations. This theory is intended to model actual numerical computations that are usually performed in floating point arithmetic. It admits classes P and NP and also an NP-complete problem. We relate the P vs NP question in this new theory to the classical P vs NP problem.

**Gregorio Malajovich**:
Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric .
*Foundations of Computatioval Mathematics*
(2018).

**ABSTRACT: **
This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of \(n\)-variate polynomial equations is specified through \(n\) monomial bases. The natural locus for the roots of those systems is known to be a certain toric variety. This variety is a compactification of \((\mathbb C\setminus\{0\})^n\), dependent on the monomial bases. A toric Newton operator is defined on that toric variety. Smale's alpha theory is generalized to provide criteria of quadratic convergence. Two condition numbers are defined and a higher derivative estimate is obtained in this setting. The Newton operator and related condition numbers turn out to be invariant through a group action related to the momentum map. A homotopy algorithm is given, and is proved to terminate after a number of Newton steps which is linear on the condition length of the lifted homotopy path. This generalizes a result from Shub (2009).

**Gregorio Malajovich**:
Computing mixed volume and all mixed cells in quermassintegral time .
*Foundations of Computational Mathematics*
**17**(5) 1293-1334
(Oct. 2017).

**ABSTRACT: **
The mixed volume counts the roots of generic sparse polynomial systems. Mixed cells are used to provide starting systems for homotopy algorithms that can find all those roots and track no unnecessary path. Up to now, algorithms for that task were of enumerative type, with no general non-exponential complexity bound. A geometric algorithm is introduced in this paper. Its complexity is bounded in the average and probability-one settings in terms of some geometric invariants: quermassintegrals associated with the tuple of convex hulls of the support of each polynomial. Besides the complexity bounds, numerical results are reported. Those are consistent with an output-sensitive running time for each benchmark family where data are available. For some of those families, an asymptotic running time gain over the best code available at this time was noticed.

**Gregorio Malajovich**:
Average mixed volume under projection .
Preprint arXiv:1410.5756
(December 2014).

**ABSTRACT: **
Abstract. The average mixed volume of a random projection of d convex bodies in Rn is bounded above in terms of a quermassintegral.

**Gregorio Malajovich**:
On the expected number of zeros of nonlinear equations .
*Foundations of Computational Mathematics*
**13**(6) pp 867-884
(dec. 2013).

**ABSTRACT: **
This paper investigates the expected number of roots of nonlinear equations. Those equations are assumed to be analytic, and to belong to certain inner product spaces. Those spaces are then endowed with the Gaussian probability distribution.

The root count on a given domain is proved to be `additive' with respect to a product operation of functional spaces. This allows to deduce a general theorem relating the expected number of roots for unmixed and mixed systems. Examples of root counts for equations that are not polynomials nor exponential sums are given at the end.

**Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub**:
Adaptive Step Size Selection for Homotopy Methods to Solve Polynomial Equations .
*IMA Journal of Numerical Analysis*
**33**, 1-29
(2013).

**ABSTRACT: **
Given a \(C^1\) path of systems of homogeneous polynomial equations \(f_t\), \(t \in [a,b]\) and an approximation \(x_a\) to a zero \(\zeta_a\) of the initial system \(f_a\), we show how to adaptively choose the step size for a Newton based homotopy method so that we approximate the lifted path \((f_t,\zeta_t)\) in the space of (problems, solutions) pairs.

The total number of Newton iterations is bounded in terms of the length of the lifted path in the condition metric.

**Felipe Cucker, Teresa Krick, Gregorio Malajovich and Mario Wschebor**:
A numerical algorithm for zero counting III: Randomization and Condition .
*Advances in Applied Mathematics*
**48**-1, pp. 215-248
(January 2012).

**ABSTRACT: **
In a recent paper [A numerical algorithm
for zero counting I: complexity and accuracy . J. of Complexity
**24** 5-6, pp 582-605 (Oct-Dec 2008)] we analyzed a
numerical algorithm for computing the number of real zeros
of a polynomial system. The analysis relied on a condition
number \(\kappa(f)\) for the input system \(f\). In this paper
we look at \(\kappa(f)\) as a
random variable derived from imposing a probability measure
on the space of polynomial systems and give bounds for both the tail
\(\mathbb P\{\kappa(f)> a\}\) and the expected value \(\mathbb E(\log\kappa(f))\).

**Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub**:
Convexity properties of the condition number II .
*SIAM Journal on Matrix Analysis and Applications*
**33**(3) pp 905--939
(Aug. 2012).

**ABSTRACT: **
In our previous paper [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1491--1506], we studied the condition metric in the space of maximal rank imes m$ matrices. Here, we show that this condition metric induces a Lipschitz Riemannian structure on that space. After investigating geodesics in such a nonsmooth structure, we show that the inverse of the smallest singular value of a matrix is a log-convex function along geodesics. We also show that a similar result holds for the solution variety of linear systems. Some of our intermediate results such as those on the second covariant derivative or Hessian of a function with symmetries on a manifold, and those on piecewise self-convex functions, are of independent interest. Those results were motivated by our investigations on the complexity of path-following algorithms for solving polynomial systems.

**Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub**:
Convexity properties of the condition number .
*SIAM Journal on Matrix Analysis and Applications*
**31** No 3, pp 1491-1506
(January 2010).

**ABSTRACT: **
We define in the space of *n x m* matrices of rank *n*, *n ≤ m*, the condition Riemannian structure as follows: For a given matrix *A* the tangent space at *A* is equipped with the Hermitian inner product obtained by multiplying the usual Frobenius inner product by the inverse of the square of the smallest singular value of *A* denoted *σ _{n}(A)*.
When this smallest singular value has multiplicity

**Felipe Cucker, Teresa Krick, Gregorio Malajovich and Mario Wschebor**:
A numerical algorithm for zero counting II: Distance to ill-posedness and smoothed analysis .
*Journal of Fixed Point Theory and Applications*
**6** No 2, pp 285-294
(Dec. 2009).

**ABSTRACT: **
We show a Condition Number Theorem for the condition number of zero counting for real polynomial systems. That is, we show that this condition number equals the inverse of the normalized distance to the set of ill-posed systems (i.e., those having multiple real zeros). As a consequence, a smoothed analysis of this condition number follows.

**Felipe Cucker, Teresa Krick, Gregorio Malajovich and Mario Wschebor**:
A numerical algorithm for zero counting I: complexity and accuracy .
*Journal of Complexity*
**24** Issues 5-6, pp 582-605
(Oct-Dec 2008).

**ABSTRACT: **
We describe an algorithm to count the number of distinct
real zeros of a polynomial (square) system *f*. The algorithm performs
$*O(nD kappa(f))*
iterations where *n* is the number of polynomials (as well as the
dimension of the ambient space), *D* is a bound on the polynomials'
degree, and *kappa(f)* is a condition number for the system. Each
iteration
uses an exponential number of operations. The algorithm uses
finite-precision arithmetic and a polynomial bound for the precision
required to ensure the returned output is correct which is
polynomial in *n*, *D* and *kappa* and logarithmic in
*kappa*
The algorithm parallelizes well in the sense that
each iteration can be computed in parallel polynomial time with an
exponential number of processors.

**Jean-Pierre Dedieu and Gregorio Malajovich**:
On the number of minima of a random polynomial .
*Journal of Complexity*
**24**, pp 89--108
(2008).

**ABSTRACT: **
We give the upper bound *sqrt(2) (d-1) ^{(n+1)/2})* for the
expected number
of critical points of a normal random polynomial with degree at most

for the expected number of minima of such a polynomial (here

**Gregorio Malajovich and Klaus Meer**:
Computing Multi-Homogeneous Bézout Numbers is Hard .
*Theory of Computing Systems*
**40** pp 553-570
(2007).

**ABSTRACT: **
The multi-homogeneous Bézout number is a bound for
the number of solutions of a system of multi-homogeneous
polynomial equations, in a suitable product of projective
spaces.
Given an arbitrary, not necessarily multi-homogeneous
system, one can ask for the optimal multi-homogenization
that would minimize the Bézout number.
In this paper, it is proved that the problem of computing,
or even estimating the optimal multi-homogeneous Bézout
number is actually *NP*-hard.
In terms of approximation theory for combinatorial
optimization, the problem of computing the best
multi-homogeneous structure does not belong to *APX*,
unless *P = NP*.
Moreover, polynomial time algorithms for estimating
the minimal multihomogeneous Bézout number up to a
fixed factor cannot exist even in a randomized setting,
unless *BPP* contains *NP*.

A conference version was published in:
*STACS 2005, Stuttgards*. Lecture Notes in Computer
Science **3404** pp. 244-255, Springer Verlag, Berlin, 2005.

**Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub**:
On the Curvature of the Central Path of Linear Programming Theory .
*Foundations of Computational Mathematics*
**5** pp 145-171
(2005).

**ABSTRACT: **
We prove a linear bound on
the average total curvature of the central path of linear
programming theory in terms on the number of independent variables
of the primal problem, and independent on the number of
constraints.

**Gregorio Malajovich and J.Maurice Rojas**:
High probability analysis of the condition number of sparse polynomial systems .
*Theoretical Computer Science*
**315**(2-3) pp. 525-555
(2004).

**ABSTRACT: **
Let *f:=(f ^{i},...,f^{n})* be
a random polynomial system
with fixed

We also consider polynomials with real coefficients
and give bounds for the expected number of real roots
and (restricted) condition number. Using a Kähler
geometric framework throughout, we also express the
expected number of roots of *f* inside a region
*U* as
the integral over *U* of a certain mixed volume form,
thus recovering the classical mixed volume when
*U = ( C^{*})^{n}*.

Note: this paper supersedes

**Jean-Pierre Dedieu, Pierre Priouret and Gregorio Malajovich**:
Newton Method on Riemannian Manifolds:
Covariant Alpha-Theory .
*IMA Journal of Numerical Analysis*
**23**-3 pp 395-419
(2003).

**ABSTRACT: **
In this paper we study quantitative aspects of Newton method for
finding zeros of mappings *f: M^{n}
->
R^{n}* and vector fields

**Gregorio Malajovich and J.Maurice Rojas**:
Polynomial Systems and the Momentum Map .
*in: Cucker and Rojas (editors), Foundations of Computational Mathematics (Proceedings of SMALEFEST 2000)*
World Scientific, Singapore
(2002).

**ABSTRACT: **
This paper outlines a Kahler-geometric approach to the study of
random sparse polynomial systems, with a view toward understanding
the distribution of solutions and their numerical conditioning.

**Gregorio Malajovich**:
Lower bounds for some decision problems over C .
*Theoretical Computer Science*
**276**Pages 425-434
(2002).

**ABSTRACT: **
Lower bounds for some explicit decision problems over the
complex numbers are given

**Gregorio Malajovich**:
On a transfer theorem for the *P ≠ NP* Conjecture .
*Journal of Complexity*
**17**(1)(pp. 27-85)
(March 2001).

**ABSTRACT: **
A model of computation is defined over the
algebraic numbers and over number fields. This model
is non-uniform, and the cost of operations depends on
the height of the operands and on the degree of the
extension of the rational defined by those operands.

A transfer theorem for the *P ≠ NP* Conjecture is proved,
namely: *P≠NP* in this model over the real algebraic
numbers if and only if *P≠NP* in the classical setting.

**Gregorio Malajovich and Jorge P. Zubelli**:
Tangent Graeffe Iteration .
*Numerische Mathematik*
**89** pp. 749-782
(2001).

**ABSTRACT: **
Graeffe iteration was the choice algorithm for solving univariate
polynomials in the XIX-th and early XX-th century. In this paper,
a new variation of Graeffe iteration is given, suitable to
IEEE floating-point arithmetics of modern digital computers.

We prove that under a certain generic assumption the proposed
algorithm converges. We also estimate the error after *N* iterations
and the running cost.

The main ideas from which this algorithm is built are: classical Graeffe iteration and Newton Diagrams, changes of scale (renormalization), and replacement of a difference technique by a differentiation one. The algorithm was implemented successfully and a number of numerical experiments are displayed.

We thank Mike McNamee for finding and helping to fix a series of typos in the published paper (see the errata below).

**Gregorio Malajovich and Jorge P. Zubelli**:
On the Geometry of Graeffe Iteration .
*Journal of Complexity*
**17** pp.541-573
(2001).

**ABSTRACT: **
A new version of the Graeffe's algorithm for finding all
the roots of univariate complex polynomials is
proposed.
It is obtained from the classical algorithm by a process
analogous to renormalization of dynamical systems.

This iteration is called Renormalized Graeffe Iteration. It is globally convergent, with probability 1. All quantities involved in the computation are bounded, once the initial polynomial is given (with probability 1). This implies remarkable stability properties for the new algorithm, thus overcoming known limitations of the classical Graeffe algorithm.

If we start with a degree-d polynomial, each renormalized
Graeffe iteration costs *O(d ^{2})* arithmetic operations, with
memory

A probabilistic global complexity bound is given. The case of univariate real polynomials is briefly discussed.

A numerical implementation of the algorithm presented herein allowed us to solve random polynomials of degree up to 1000.

**James Demmel, Benjamin Diament and Gregorio Malajovich**:
On the Complexity of computing error bounds .
*Foundations of Computational Mathematics*
**1**(1) pp 101-125
(2001).

**ABSTRACT: **
We consider the cost of estimating an error bound for the computed
solution of a system of linear equations, i.e. estimating the
norm of a matrix inverse. Under some technical assumptions we show
that computing even a coarse
error bound for the solution
of a triangular system of equations costs at least as much as testing
whether the product of two matrices is zero. The complexity of the
latter problem is in turn conjectured to be the same as matrix multiplication,
matrix inversion, etc. Since most error bounds in practical use have
much lower complexity, this means they must sometimes exhibit large errors.
Our results hold for the RAM model with
bit complexity, as well as computations over rational and algebraic numbers,
but not real or complex numbers. Our results also extend to estimating
error bounds or condition numbers
for other linear algebra problems such as computing eigenvectors.

Most of condition estimation algorithms currently in use seem to satisfy
the following properties:
they perform at least one operation on each matrix entry, and they
are arbitrarily faster than any zero tester. It is shown that any
condition estimator satisfying those assumptions will give
estimates
wrong of a factor *2 ^{γ k + τ(n)}*, where

**Gregorio Malajovich**:
Condition number bounds for problems with integer coefficients .
*J. of Complexity*
**16**(3) 529-551
(2000).

**ABSTRACT: **
An apriori bound for the condition number associated to
each of the following problems is given: general linear
equation solving, minimum squares, non-symmetric eigenvalue
problems, solving univariate polynomials, solving systems
of multivariate polynomials. It is assumed that the input
has integer coefficients and is not on the degenerate locus
of the respective problem (i.e. the condition number is
finite). Then condition numbers are bounded in terms of the
dimension and of the bit-size of the input.

In the same setting, bounds are given for the speed of convergence of the following iterative algorithms: QR without shift for the symmetric eigenvalue problem, and Graeffe iteration for univariate polynomials.

**Gregorio Malajovich**:
Ultimate Polynomial Time .
*Unpublished*
MSRI Preprint 1999-03
(1999).

**ABSTRACT: **
The class *UP* of `ultimate polynomial time'
problems over * C* is introduced; it contains the class

A notion of `ultimate complexity' of a problem is suggested. It provides lower bounds for the complexity of structured problems.

**Gregorio Malajovich and Klaus Meer**:
On the structure of *NP(C)*. .
*SIAM Journal on Computing*
**28**(1) pp 27-35
(1998).

**ABSTRACT: **
This paper deals with complexity classes *P( C)*
and

**Gregorio Malajovich and Jorge P. Zubelli**:
A fast and stable algorithm for splitting polynomials .
*Computers & Mathematics with Applications*
**33**(3) pp.1-23
(1997).

**ABSTRACT: **
A new algorithm for splitting polynomials is presented.
This algorithm requires *O(d *log*(1/ε)) ^{1+δ}* floating
point operations, with

An important application of the method is factorizing polynomials or polynomial root-finding.

**Gregorio Malajovich**:
On generalized Newton algorithms : Quadratic convergence, path-following and error analysis .
*Theoretical Computer Science*
**133** No 65-84
(1994).

**ABSTRACT: **
Newton iteration is known (under some precise conditions) to converge
quadratically to zeros of non-degenerate systems of polynomials.
This and other properties may be used to obtain theorems on the
global complexity of solving systems of polynomial equations
(See Shub and Smale in [Bezout1]), using a model of computability
over the reals.

However, it is not practical (and not desirable) to actually compute Newton iteration exactly. In this paper, approximate Newton iteration is investigated for several generalizations of the Newton operator. Quadratic covergence theorems and a robustness theorem are extended to approximate Newton iteration, generalizing some of the results in [Bezout1]. The results here can be used to prove complexity theorems on path following algorithms for solving systems of polynomial equations, using a model of computation over the integers ([Malajovich])