Bürgisser, Peter(D-BONN-IF); Karpi\'nski, Marek(D-BONN-IF); Lickteig, Thomas(D-BONN-IF)

Festschrift for Joseph F. Traub, Part II.

The paper studies the impact of randomization on the complexity of deciding membership in a real semialgebraic set $X$. The problem has significance in the area of efficient tests for algebraic computations. Some examples are exhibited where randomization presents signficant improvement over deterministic methods. A theoretical framework is given to describe randomized algebraic decision-tree computations. A general lower bound on the randomized complexity of the membership problem in irreducible real algebraic subsets is proved. The general bound is applied to various interesting subsets to obtain explicit lower bounds. These include the case when $X$ is a generic complete intersection of polynomials of the same degree. Some nongeneric cases, including the graphs of elementary symmetric functions, ${\rm SL}(m,\bold R)$, and determinantal varieties are also considered. For example, the lower bound is essentially optimal for the graph of all elementary symmetric functions. The bound for ${\rm SL}(m,\bold R)$ has the same magnitude as the complexity of matrix multiplication.

\{For the entire collection see MR 93m:00048\}.