Publication Details
Title: On Randomized Algebraic Test Complexity
Author: P. Buergisser, M. Karpinski, and T. Lickteig
Group: ICSI Technical Reports
Date: October 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-070.pdf
Overview:
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].
Bibliographic Information:
ICSI Technical Report TR-92-070
Bibliographic Reference:
P. Buergisser, M. Karpinski, and T. Lickteig. On Randomized Algebraic Test Complexity. ICSI Technical Report TR-92-070, October 1992
Author: P. Buergisser, M. Karpinski, and T. Lickteig
Group: ICSI Technical Reports
Date: October 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-070.pdf
Overview:
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].
Bibliographic Information:
ICSI Technical Report TR-92-070
Bibliographic Reference:
P. Buergisser, M. Karpinski, and T. Lickteig. On Randomized Algebraic Test Complexity. ICSI Technical Report TR-92-070, October 1992