
University of Bonn > Department of Computer Science > Chair V  
CSReports 1992  Copyright 1992 University of Bonn, Department of Computer Science, Abt. V  
8580

On randomized algebraic test complexity
Peter Buergisser, Marek Karpinski, Thomas Lickteig [Download PostScript] [Download PDF] We investigate the impact of randomization on the complexity of membership in a (semi)algebraic subset $X \subset \rr^m$. Examples are exhibited where allowing for a certain error probability $\epsilon$ in the answer of the algorithms the complexity of decision problems decreases. A randomized $(\Omega^k,\{=,\leq\})$decision tree ($k \subseteq\rr$ a subfield) over $m$ will be defined as a pair $(T,\mu)$ where $\mu$ a probability measure on some $\rr^n$ and $T$ is a $(\Omega^k,\{=,\leq\})$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 \subset \rr^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, $\mbox{SL}(m,\rr)$, and determinant varieties, extending results in \cite{Li:90}. 

Last Change:
11/05/14 at 09:42:20
Deutsch 
University of Bonn > Department of Computer Science > Chair V 