On Randomized Algebraic Test Complexity

We investigate the impact of randomization on the complexity of deciding membership in a (semi-)algebraic subset X ? ?^m. Examples are exhibited where allowing for a certain error probability ? in the answer of the algorithms the complexity of decision problems decreases. A randomized (?^k,{=,?})-decision tree (k ? ? a subfield) over m will be defined as a pair (T, ?) where ? a probability measure on some ?^n and T is a (?^k,{=,?})-decision tree over m+n. We prove a general lower bound on the average decision complexity for testing membership in an irreducible algebraic subset X ? ?^m and apply it to k-generic complete intersection of polynomials of the same degree, extending results in [4, 6]. We also give applications to nongeneric cases, such as graphs of elementary symmetric functions, SL(m,?), and determinant varieties, extending results in [Li:90].

ICSI Technical Report TR-92-070

Technical Report