A note on parallel and alternating time

A long standing open question in complexity theory over the reals is the relationship between parallel time and quantifier alternation. It is known that alternating digital quantifiers is weaker than parallel time, which in turn is weaker than alternating unrestricted (real) quantifiers. In this note we consider some complexity classes defined through alternation of mixed digital and unrestricted quantifiers in different patterns. We show that the class of sets decided in parallel polynomial time is sandwiched between two such classes for different patterns.     

Complexity Lower Bounds for Approximation Algebraic Computation Trees

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.     

The complexity to compute the Euler characteristic of complex varieties

We extend one of the main results of Bürgisser and Cucker (http://www.arxiv.org/abs/cs/cs.CC/0312007), which asserts that the computation of the Euler characteristic of a semialgebraic set is complete in the counting complexity class ${\mathrm{FP}}_{\mathbb{R}}^{\mathrm{\#}{\mathrm{P}}_{\mathbb{R}}}$. The goal is to prove a similar result over $\mathbb{C}$: the computation of the Euler characteristic of an affine or projective complex variety is complete in the class ${\mathrm{FP}}_{\mathbb{C}}^{\mathrm{\#}{\mathrm{P}}_{\mathbb{C}}}$. To cite this article: P. Bürgisser et al., C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis

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.     

Computing the Homology of Real Projective Sets

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of real projective varieties. Here numerical means that the algorithm is numerically stable (in a sense to be made precise). Its cost depends on the condition of the input as well as on its size and is singly exponential in the number of variables (the dimension of the ambient space) and polynomial in the condition and the degrees of the defining polynomials. In addition, we show that outside of an exceptional set of measure exponentially small in the size of the data, the algorithm takes exponential time.     

Machines Over the Reals and Non-Uniformity

We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet - say {0,1} - which can be decided by real machines working under several resource restrictions. Non-uniformity appears here in a natural way. However, since this is a technical concept which is not widely known, we summarize in Section 2 some of the intuitive notions, as well as a few basic theorems related to it. In Section 3 we do this for the subject of real machines and then, in Section 4 we present the state of the art of the surveyed topic. We devote Section 1 to introduce the main concepts of complexity theory. Proofs in this article are quite sketchy and are included more to convey intuitive ideas than to completely prove the claimed statements. Bibliographical references to the original literature are supplied for the latter purpose.     

Round-off estimates for second-order conic feasibility problems

We present the analysis of an interior-point method to decide feasibility problems of second-order conic systems. A main feature of this algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited.     

A new condition number for linear programming

In this paper we define a new condition number ?(A) for the following problem: given a m by n matrix A, find x∈ℝ ⁿ , s.t. Ax<0. We characterize this condition number in terms of distance to ill-posedness and we compare it with existing condition numbers for the same problem. Received: November 5, 1999 / Accepted: November 2000?Published online September 17, 2001