These pages are a first attempt to compare the efficiency of symbolic and numerical analysis
procedures that solve systems of multivariate polynomial equations. In particular, we …

We show lower bounds for depth of arithmetic networks over algebraically closed fields, real
closed fields and the field of the rationals. The parameters used are either the degree or the …

We show several arithmetic estimates for Hilbert's Nullstellensatz. This includes an
algorithmic procedure computing the polynomials and constants occurring in a Bézout …

We investigate the impact of randomization on the complexity of deciding membership in a
(semi-) algebraic subset X⊂ R m. Examples are exhibited where allowing for a certain error …

We investigate the complexity of algebraic decision trees deciding membership in a
hypersurface X⊂ C m. We prove an optimal lower bound on the number of additions …

We introduce and analyze the concept of generic width of a semialgebraic set, showing that
it gives lower bounds for decisional complexities. By means of the computation of the …

Semi-algebraic decision complexity introduces a quantitative finiteness aspect into semi-
algebraic geometry. In this paper we combine methods from abstract real algebraic …

We prove upper bounds on the number of L p-spheres passing through D+ 1 points in
general position in D-space, and on the sum of the Betti numbers of the intersection of …

The topic of this paper is the complexity of algebraic decision trees deciding membership in
an algebraic subset X⊆ R m where R is a real or algebraically closed field. We define a …

This note reflects an extension of the methods of HE Warren for obtaining lower bounds for
approximations of a compact class of continuous functions. We extend his lower bounds to …