On randomized semi-algebraic test complexity

DOI10.1006/JCOM.1993.1016MaRDI QIDQ1260656zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Marek Karpinski, Thomas Lickteig

Publication date 24 August 1993

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.1993.1016

zbMATH Keywords

randomized decision complexityrandomized decision trees

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The influence of randomization on the complexity of deciding the membership to semi-algebraic set is discussed. In some cases when a probability error in the answer is allowed, the complexity decreases. A general lower bound on the randomized decision complexity is obtained in the case of an irreducible algebraic set and extended to the case of generic complete intersections of polynomials with the same degree. Some applications to non generic cases (in particular to symmetric functions) are also given. In the introduction various examples are discussed, the next section is devoted to a precise definition of randomized decision trees, then a general lower bound is given and various applications are presented.

Recommendations

• Semi-algebraic decision complexity, the real spectrum, and degree
• A lower bound for randomized algebraic decision trees
• scientific article; zbMATH DE number 1984321
• scientific article; zbMATH DE number 1256781

Cited in

(11)

• A lower bound for randomized algebraic decision trees
• Randomization and the computational power of analytic and algebraic decision trees
• On the decisional complexity of problems over the reals
• Semi-algebraic decision complexity, the real spectrum, and degree
• Complexity bounds for zero-test algorithms
• A tight lower bound for computing the diameter of a 3D convex polytope
• scientific article; zbMATH DE number 5999718 (Why is no real title available?)
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• scientific article; zbMATH DE number 1775407 (Why is no real title available?)
• Nondeterministic seedless oritatami systems and hardness of testing their equivalence
• On certain computable tests and componentwise error bounds

This page was built for publication: On randomized semi-algebraic test complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260656)