Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1992 Copyright 1992 Universität Bonn, Institut für Informatik, Abt. V

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
Universität Bonn -> Institut für Informatik -> Abteilung V