On randomized semi-algebraic test complexity (Q1260656)

The influence of randomization on the complexity of deciding the membership to semi-algebraic set is discussed. In some cases when a probability error in the answer is allowed, the complexity decreases. A general lower bound on the randomized decision complexity is obtained in the case of an irreducible algebraic set and extended to the case of generic complete intersections of polynomials with the same degree. Some applications to non generic cases (in particular to symmetric functions) are also given. In the introduction various examples are discussed, the next section is devoted to a precise definition of randomized decision trees, then a general lower bound is given and various applications are presented.