|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-Reports 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 |